第一次用dijkstrea
(待補詳解)
//first time to ude dijistra #include <iostream> #include <stdio.h> #include <cstring> #include <utility> #include <queue> #include <algorithm> #include <vector> #include <cassert> using namespace std; #define MP make_pair #define F first #define S second typedef pair<int,int> pii; typedef pair<int,pii> piii; const int MAX_N = 1e4 + 6; const int MAX_M = 1e5 + 6; const int INF = 1e9 + 7; vector<pii> edg[MAX_N]; int a[MAX_M],b[MAX_M],p[MAX_M],q[MAX_M],r[MAX_M]; int d[MAX_N]; #define int long long main () { if (fopen("gpsduel.in","r")) { freopen("gpsduel.in","r",stdin); freopen("gpsduel.out","w",stdout); } // freopen("5.in","r",stdin); int n,m; while (scanf("%lld %lld",&n,&m) != EOF) { for (int x=0;n>=x;x++) { edg[x].clear(); } for (int x=1;m>=x;x++) { scanf("%lld %lld %lld %lld",&a[x],&b[x],&p[x],&q[x]); a[m+x]=b[x]; b[m+x]=a[x]; p[m+x]=p[x]; q[m+x]=q[x]; edg[a[x]].push_back(make_pair(b[x],x)); edg[b[x]].push_back(make_pair(a[x],m+x)); r[x] = 2; r[m+x] = 2; } //decide route P priority_queue<piii,vector<piii>,greater<piii> > pq; fill(d,d+MAX_N,INF); d[n]=0; pq.push(MP(0,MP(n,2*m+1))); //value,to,from(the id) while (!pq.empty()) { piii tmp=pq.top(); pq.pop(); int t=tmp.S.F; if (d[t] < tmp.first) continue; else if (d[t] == tmp.first) { if (tmp.second.S!=2*m+1) r[(tmp.second.S>m?tmp.second.S-m:tmp.S.S+m)]--; if (tmp.second.S!=2*m+1) continue; } else if (d[t] > tmp.first) { if (tmp.second.S!=2*m+1) r[(tmp.second.S>m?tmp.second.S-m:tmp.S.S+m)]--; d[t]=tmp.first; } for (auto i=edg[t].begin();i!=edg[t].end();i++) { pii tmp=*i; int x=tmp.first,y=tmp.second; if (y<=m) continue; if (d[x] >= d[t] + p[y]) { pq.push(MP(d[t] + p[y],MP(x,y))); } } } // for (int x=1;2*m>=x;x++) cout<<"r["<<x<<"] = "<<r[x]<<endl; //decide route Q fill(d,d+MAX_N,INF); d[n]=0; pq.push(MP(0,MP(n,2*m+1))); //value,to,from(the id) while (!pq.empty()) { piii tmp=pq.top(); pq.pop(); int t=tmp.S.F; if (d[t] < tmp.first) continue; else if (d[t] == tmp.first) { if (tmp.second.S!=2*m+1) r[(tmp.second.S>m?tmp.second.S-m:tmp.S.S+m)]--; if (tmp.second.S!=2*m+1) continue; } else if (d[t] > tmp.first) { if (tmp.second.S!=2*m+1) r[(tmp.second.S>m?tmp.second.S-m:tmp.S.S+m)]--; d[t]=tmp.first; } for (auto i=edg[t].begin();i!=edg[t].end();i++) { pii tmp=*i; int x=tmp.first,y=tmp.second; if (y<=m) continue; if (d[x] >= d[t] + q[y]) { pq.push(MP(d[t] + q[y],MP(x,y))); } } } // for (int x=1;2*m>=x;x++) { // if (r[x] < 0)cout<<"r["<<x<<"] = "<<r[x]<<endl; // assert(0<=r[x]); // } //count the answer now fill(d,d+MAX_N,INF); d[1]=0; pq.push(MP(0,MP(1,2*m+1))); //value,to,from(the id) while (!pq.empty()) { assert(pq.size() <= m); piii tmp=pq.top(); pq.pop(); int t=tmp.S.F; // cout<<"t = "<<t<<endl; if (d[t] <= tmp.first && t!=1) continue; if (d[t] > tmp.first) { d[t] = tmp.first; } for (auto i=edg[t].begin();i!=edg[t].end();i++) { pii tmp=*i; int x=tmp.first,y=tmp.second; if (y>m) continue; if (d[x] > d[t] + r[y]) { pq.push(MP(d[t] + r[y],MP(x,y))); } } } printf("%lld\n",d[n]); } }
