单源最短路，我拿SPFA写的，题目坑人，明明写的是没有其他路可走的时候才能等，结果是一直可以等。还有就是要拿更新后的d[u]操作，而不是进入队列的first
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <queue> using namespace std; int n,m,s,t; const int maxm=50000+100; const int maxn=300+100; const int inf=0x3f3f3f3f; typedef pair<int,int> pp; struct note { int u,v,op,cl,w; bool operator < (note &p) const { return w<p.w; } } aa[maxm]; int d[maxn],vis[maxn]; void spfa() { queue<pp> q; memset(vis,0,sizeof(vis)); memset(d,inf,sizeof(d)); d[s]=0; q.push(make_pair(0,s)); while(q.size()) { pp p=q.front(); q.pop(); int u=p.second; vis[u]=0; for(int i=1; i<=m; i++) if(u==aa[i].u) { int v=aa[i].v; if(aa[i].op<aa[i].w) continue; if(d[u]%(aa[i].cl+aa[i].op)+aa[i].w<=aa[i].op)//能直接通过，不用等 { if(d[v]>d[u]+aa[i].w) { d[v]=d[u]+aa[i].w; if(!vis[v]) { q.push(make_pair(d[v],v)); vis[v]=1; } } } else//需要等一下 { int ff=aa[i].cl+aa[i].op-d[u]%(aa[i].cl+aa[i].op)+aa[i].w; if(d[v]>d[u]+ff) { d[v]=d[u]+ff; if(!vis[v]) { q.push(make_pair(d[v],v)); vis[v]=1; } } } } } printf("%d\n",d[t]); } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int Case=0; while(~scanf("%d%d%d%d",&n,&m,&s,&t)) { for(int i=1; i<=m; i++) scanf("%d%d%d%d%d",&aa[i].u,&aa[i].v,&aa[i].op,&aa[i].cl,&aa[i].w); printf("Case %d: ",++Case); spfa(); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/8358886.html
