这题仍然可以跑dijkstra，只是在通过边的时候边的权值不再是通过时间，还要通过数学计算加上一些等待时间
#include <cstdio> #include <iostream> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <cstdlib> #include <utility> #include <map> #include <stack> #include <set> #include <vector> #include <queue> #include <deque> #include <sstream> #define x first #define y second #define mp make_pair #define pb push_back #define LL long long #define Pair pair<int,int> #define LOWBIT(x) x & (-x) using namespace std; const int MOD=1e9+7; const int INF=0x7ffffff; const int magic=348; struct node { int to,cap,open,close; }; vector<node> v[548]; int n,e,s,t; int dist[548]; priority_queue<Pair> q; int calc(int time,node edge) { int res=0; if (time%(edge.open+edge.close)>edge.open) { res+=(edge.open+edge.close)-time%(edge.open+edge.close); res+=edge.cap; return res; } if (edge.open-time%(edge.open+edge.close)>=edge.cap) return edge.cap; else { res+=edge.open-time%(edge.open+edge.close); res+=edge.close; res+=edge.cap; return res; } } void dijkstra() { int i,x,y,dd;node edge; for (i=1;i<=n;i++) dist[i]=INF; dist[s]=0;q.push(mp(0,s)); while (!q.empty()) { x=q.top().y;dd=-q.top().x;q.pop(); if (dd>dist[x]) continue; //cout<<x<<endl; for (i=0;i<v[x].size();i++) { edge=v[x][i];y=edge.to; int tt=calc(dist[x],edge); //cout<<tt<<endl; //cout<<dist[y]<<' '<<dist[x]+tt<<endl; if (dist[y]>dist[x]+tt) { dist[y]=dist[x]+tt; q.push(mp(-dist[y],y)); } } } } int main () { int i,ca=0,start;node ins; while (scanf("%d%d%d%d",&n,&e,&s,&t)!=EOF) { for (i=1;i<=n;i++) v[i].clear(); for (i=1;i<=e;i++) { scanf("%d",&start); scanf("%d%d%d%d",&ins.to,&ins.open,&ins.close,&ins.cap); if (ins.cap>ins.open) continue; v[start].pb(ins); } dijkstra(); //for (i=1;i<=n;i++) cout<<dist[i]<<' '; //cout<<endl; printf("Case %d: %d\n",++ca,dist[t]); } return 0; }