这是一道很典型的单源点最短路径问题,用Dij来解,记录路径,通过dfs来输出路径
代码如下:
#include <cstdio> #include <cstring> const int N = 20; const int INF = 100000000; int n, s, t, ans, icase; int g[N][N], d[N], p[N]; void dij() { int mi, v; for ( int i = 1; i <= n; ++i ) d[i] = INF; d[s] = 0, ans = 0; bool vis[N]; memset( vis, 0, sizeof(vis) ); for ( int u = 0; u < n; ++u ) { mi = INF; for ( int i = 1; i <= n; ++i ) if ( !vis[i] && d[i] < mi ) mi = d[i], v = i; vis[v] = true; for ( int i = 1; i <= n; i++ ) if ( !vis[i] && g[v][i] >= 0 && d[i] > d[v] + g[v][i] ) d[i] = d[v] + g[v][i], p[i] = v; } } void output( int x ) { if ( x == -1 ) return; output( p[x] ); if ( p[x] != -1 ) printf(" "); printf("%d", x); return; } int main() { icase = 1; while ( scanf("%d", &n) != EOF && n ) { for ( int i = 1; i <= n; p[i] = -1, ++i ) for ( int j = i; j <= n; ++j ) g[i][j] = g[j][i] = -1; for ( int i = 1; i <= n; ++i ) { int num; scanf("%d", &num); for ( int j = 1; j <= num; ++j ) { int v, del; scanf("%d %d", &v, &del); g[i][v] = del; } } scanf("%d%d", &s, &t); dij(); printf("Case %d: Path = ", icase++); output( t ); printf("; %d second delay\n", d[t]); } }