这道题坑在三个地方:
第一,是忽略dij的最外层循环的次数应该是出现的节点的个数,而不是26次;
第二,是忽略了除数为0的情况;
第三,是输入的问题,以后输入单独的字符,都用字符串来处理
代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 30; const int INF = 0x3fffffff; int T, M, n, cnt; int g[N][N], tb[N][N], d[N], vis[N]; bool node[30]; int tim( int sec, int i, int j ) { if ( tb[i][j] == 0 || sec/tb[i][j]%2 ) return 0; return tb[i][j] - sec%tb[i][j]; } int Dijsktra( int S, int E ) { int imax, mark, u; d[S] = 0; memset( vis, 0, sizeof(vis)); for ( u = 0; u < n; ++u ) { imax = INF; for ( int i = 0; i < 26; ++i ) if ( !vis[i] && imax > d[i] ) imax = d[mark=i]; vis[mark] = true; //cout << imax << endl; for ( int i = 0; i < 26; ++i ) { if ( !vis[i] && g[mark][i] > 0 ) { int tmp = tim(d[mark]+g[mark][i], mark, i); if ( d[i] > d[mark] + g[mark][i] + tmp ) d[i] = d[mark] + g[mark][i] + tmp; } } } return d[E]; } void init() { for ( int i = 0; i < N; ++i ) { d[i] = INF; } memset( g, -1, sizeof(g)); memset( tb, -1, sizeof(tb)); memset( node, 0, sizeof(node)); n = cnt = 0; } int main() { while(scanf("%d", &T)!= EOF ) { while ( T-- ) { scanf("%d", &M); init(); char ss[5], ee[5]; int u, v, dis, rgt; while ( M-- ) { getchar(); scanf("%s %s %d %d", ss, ee, &dis, &rgt); u = ss[0] - 'a'; v = ee[0] - 'a'; if ( !node[u] ) { node[u] = true; n++; } if ( !node[v] ) { node [v] = true; n++; } g[u][v] = dis, tb[u][v] = rgt; } getchar(); scanf("%s%s", ss, ee); u = ss[0] - 'a'; v = ee[0] - 'a'; printf("%d\n", Dijsktra( u, v )); } } }