ネタバレ：Minimum Cost Flowは必要なかった。
全部 ai > biのときは、分岐するのが無駄と分かるので最短路。
ai < biが一本あっても別にそこを流れる流量を決めうちすればよい。
↑の流量の候補は実は定数個らしくて決めうちを上手くやればWarshall-Floydでも余裕らしい。なるほどね。
サンプルが異常に弱くて ai < bi があるケースが1個しかない。何事。
#include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; struct edge{ int t,a,b,d; edge(){} edge(int t,int a,int b,int d):t(t),a(a),b(b),d(d){} }; vector<edge>g[120]; vector<edge>rev[120]; int w[120][120]; int ijk[120][5]; int v[120][5]; int main(){ int n,m,s,t,f; scanf("%d%d%d%d%d",&n,&m,&s,&t,&f); int cnt=0; int p,q; int A,B,D; for(int i=0;i<m;i++){ int a,b,c,d,e; scanf("%d%d%d%d%d",&a,&b,&c,&d,&e); g[a].push_back(edge(b,c,d,e)); rev[b].push_back(edge(a,c,d,e)); if(c<d){ cnt++; p=a; q=b; A=c;B=d;D=e; } } for(int i=0;i<n;i++)for(int j=0;j<n;j++){ if(i==j)w[i][j]=0; else w[i][j]=999999999; } for(int i=0;i<n;i++){ for(int j=0;j<g[i].size();j++){ if(g[i][j].a<g[i][j].b)continue; w[i][g[i][j].t]=min(w[i][g[i][j].t],g[i][j].a*min(f,g[i][j].d)+g[i][j].b*max(0,f-g[i][j].d)); } } for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++){ w[i][j]=min(w[i][j],w[i][k]+w[k][j]); } if(cnt==0){ if(w[s][t]>888888888)printf("Impossible\n"); else printf("%d\n",w[s][t]); return 0; } int ret=w[s][t]; for(int i=1;i<=f;i++){ int co=A*min(i,D)+B*max(0,i-D); for(int j=0;j<n;j++)for(int k=0;k<5;k++){ v[j][k]=0; ijk[j][k]=999999999; } priority_queue<pair<int,pair<int,int> > >Q; ijk[p][3]=0; ijk[q][4]=0; Q.push(make_pair(0,make_pair(p,3))); Q.push(make_pair(0,make_pair(q,4))); while(Q.size()){ int cost=-Q.top().first; int at=Q.top().second.first; int type=Q.top().second.second; Q.pop(); if(v[at][type])continue; v[at][type]=1; if(type==3){ for(int j=0;j<rev[at].size();j++){ if(rev[at][j].a<rev[at][j].b)continue; int to=rev[at][j].t; int c1=rev[at][j].a*min(i,rev[at][j].d)+rev[at][j].b*max(0,i-rev[at][j].d); if(!v[to][type]&&ijk[to][type]>cost+c1){ ijk[to][type]=cost+c1; Q.push(make_pair(-ijk[to][type],make_pair(to,type))); } } }else{ for(int j=0;j<g[at].size();j++){ if(g[at][j].a<g[at][j].b)continue; int to=g[at][j].t; int c1=g[at][j].a*min(i,g[at][j].d)+g[at][j].b*max(0,i-g[at][j].d); if(!v[to][type]&&ijk[to][type]>cost+c1){ ijk[to][type]=cost+c1; Q.push(make_pair(-ijk[to][type],make_pair(to,type))); } } } } if(i==f&&ijk[s][3]<888888888&&ijk[t][4]<888888888){ ret=min(ret,co+ijk[s][3]+ijk[t][4]); } ijk[s][0]=0; Q.push(make_pair(0,make_pair(s,0))); while(Q.size()){ int cost=-Q.top().first; int at=Q.top().second.first; int type=Q.top().second.second; Q.pop(); if(v[at][type])continue; v[at][type]=0; for(int j=0;j<g[at].size();j++){ if(g[at][j].a<g[at][j].b)continue; int to=g[at][j].t; int c1=g[at][j].a*min(f,g[at][j].d)+g[at][j].b*max(0,f-g[at][j].d); int c2=g[at][j].a*min(f-i,g[at][j].d)+g[at][j].b*max(0,f-i-g[at][j].d); if(type==1)swap(c1,c2); if(!v[to][type]&&ijk[to][type]>cost+c1){ ijk[to][type]=cost+c1; Q.push(make_pair(-ijk[to][type],make_pair(to,type))); } } int c3=ijk[at][3]; if(type==1)c3=ijk[at][4]; if(type<2&&!v[at][type+1]&&ijk[at][type+1]>cost+c3){ ijk[at][type+1]=cost+c3; Q.push(make_pair(-ijk[at][type+1],make_pair(at,type+1))); } } //printf("%d: %d %d\n",i,ijk[t][2],co); ret=min(ret,ijk[t][2]+co); } if(ret>888888888)printf("Impossible\n"); else printf("%d\n",ret); }
