题意：求一个集合到另一个集合的最小路径。
思路1：直接用循环T次Dijkstra算法，从而求得最小值，但是TLE了。后来加一个添加一个新的源点，把起点与源点路径的赋值为0就可以啦。
条件：
（1）有向图。
（2）T次Dijkstra可能会超时。
CODE：
#include <stdio.h> #include <stdlib.h> #include < string.h> using namespace std; const int SIZE = 1010; const int INF = 0x3f3f3f3f; int d[SIZE], v[SIZE]; int w[SIZE][SIZE]; int save[SIZE]; int n, m, s; void Dijkstra( int src) { int i, j; memset(v, 0, sizeof(v)); for(i = 0; i <= n; i++) d[i] = (i == src)? 0:INF; // n+1个点 for(i = 0; i <= n; i++) { int x, m = INF; for( int y = 0; y <= n; y++) if(!v[y] && m > d[y]) m = d[x=y]; // n+1个点 v[x] = 1; for( int y = 0; y <= n; y++) d[y] <?= d[x] + w[x][y]; // n+1个点 } return ; } void init() { memset(w, INF, sizeof(w)); memset(d, 0, sizeof(d)); memset(v, 0, sizeof(v)); memset(save, 0, sizeof(save)); } int main() { while(~scanf( " %d%d%d ", &n, &m, &s)) { init(); while(m--) { int u, v, cost; scanf( " %d%d%d ", &u, &v, &cost); if(cost < w[u][v]) w[u][v] = cost; } int T; scanf( " %d ", &T); for( int i = 1 ; i <= T; i++) { scanf( " %d ", &save[i]); w[ 0][save[i]] = 0; // 赋值为0 } Dijkstra( 0); if(d[s] == INF) printf( " -1\n "); else { printf( " %d\n ", d[s]); } } return 0; }
思路2：建立反向图，将终点变为源点找最小值。
CODE：
#include <stdio.h> #include <stdlib.h> #include < string.h> using namespace std; const int SIZE = 1010; const int INF = 0x3f3f3f3f; int d[SIZE], v[SIZE]; int w[SIZE][SIZE]; int save[SIZE]; int n, m, s; void Dijkstra( int src) { int i, j; memset(v, 0, sizeof(v)); for(i = 1; i <= n; i++) d[i] = (i == src)? 0:INF; for(i = 1; i <= n; i++) { int x, m = INF; for( int y = 1; y <= n; y++) if(!v[y] && m > d[y]) m = d[x=y]; v[x] = 1; for( int y = 1; y <= n; y++) d[y] <?= d[x] + w[x][y]; } return ; } void init() { memset(w, INF, sizeof(w)); memset(d, 0, sizeof(d)); memset(v, 0, sizeof(v)); memset(save, 0, sizeof(save)); } int main() { while(~scanf( " %d%d%d ", &n, &m, &s)) { init(); while(m--) { int u, v, cost; scanf( " %d%d%d ", &u, &v, &cost); if(cost < w[v][u]) // 反向单向边 w[v][u] = cost; // 反向单向边 } int T; scanf( " %d ", &T); for( int i = 1 ; i <= T; i++) scanf( " %d ", &save[i]); Dijkstra(s); int m = INF; for( int i = 1; i <= T; i++) m <?= d[save[i]]; if(m == INF) printf( " -1\n "); else { printf( " %d\n ", m); } } return 0; }