USACO 2014 US Open, Silver Problem 2. Dueling GPSs

http://www.usaco.org/index.php?page=viewproblem2&cpid=434

第一次用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]);
    }
}