最短路问题稍微复杂了一点，松弛的时候多判断一些条件就可以了。第一次用SPFA写最短路。
#include<cstdio> #include<cmath> #include<cstring> #include<vector> #include<queue> #include<algorithm> using namespace std; const int maxn = 305; vector<int> cost[maxn][maxn]; vector<int> ljb[maxn]; struct abc{ int start, end, aa, bb, cc; }dt[50005]; int flag[maxn], dist[maxn]; int n, m, sx, ex; void spfa() { int i, ii; flag[sx] = 1; for (i = 0; i <= n; i++) dist[i] = 0x7FFFFFFF; dist[sx] = 0; queue<int>Q; Q.push(sx); while (!Q.empty()) { int hh = Q.front(); Q.pop(); flag[hh] = 0; int nowtime = dist[hh]; for (ii = 0; ii < ljb[hh].size(); ii++) { for (i = 0; i < cost[hh][ljb[hh][ii]].size(); i++) { int id = cost[hh][ljb[hh][ii]][i]; if (dt[id].aa < dt[id].cc) continue; int yy = nowtime % (dt[id].aa + dt[id].bb); if (yy <= dt[id].aa) { if (yy + dt[id].cc <= dt[id].aa) { if (nowtime + dt[id].cc < dist[ljb[hh][ii]]) { dist[ljb[hh][ii]] = nowtime + dt[id].cc; if (!flag[ljb[hh][ii]])Q.push(ljb[hh][ii]), flag[ljb[hh][ii]] = 1; } } else { if (nowtime + dt[id].aa - yy + dt[id].bb + dt[id].cc < dist[ljb[hh][ii]]) { dist[ljb[hh][ii]] = nowtime + dt[id].aa - yy + dt[id].bb + dt[id].cc; if (!flag[ljb[hh][ii]])Q.push(ljb[hh][ii]), flag[ljb[hh][ii]] = 1; } } } else { if (nowtime + dt[id].aa + dt[id].bb - yy + dt[id].cc< dist[ljb[hh][ii]]) { dist[ljb[hh][ii]] = nowtime + dt[id].aa + dt[id].bb - yy + dt[id].cc; if (!flag[ljb[hh][ii]])Q.push(ljb[hh][ii]), flag[ljb[hh][ii]] = 1; } } } } } } int main() { int _ = 1; int i, j, u, v, a, b, c; while (~scanf("%d%d%d%d", &n, &m, &sx, &ex)) { for (i = 0; i <= n; i++) ljb[i].clear(); for (i = 0; i <= n; i++) for (j = 0; j <= n; j++) cost[i][j].clear(); memset(flag, 0, sizeof(flag)); for (i = 0; i < m; i++) { scanf("%d%d%d%d%d", &u, &v, &a, &b, &c); dt[i].start = u; dt[i].end = v; dt[i].cc = c; dt[i].aa = a; dt[i].bb = b; cost[u][v].push_back(i); ljb[u].push_back(v); } spfa(); printf("Case %d: %d ", _++, dist[ex]); } return 0; }