Submission #647370

#	Time	Username	Problem	Language	Result	Execution time	Memory
647370		ck_platypus	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	31 ms	5316 KiB

ho_t4

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <utility>
#include <bitset>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <queue>
#include <cstring>
#include <fstream>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pll pair<ll, ll>
#define plpll pair<ll, pll>
#define pii pair<int, int>
#define f first
#define s second
#define inf 1000000000000000000
#define endl '\n'
struct edge{
    ll u, v, c, d;
};

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n, m;
    cin >> n >> m;
    vector<pll> G[n+1], g[n+1];
    edge z;
    vector<edge> e;
    while(m--){
        cin >> z.u >> z.v >> z.c >> z.d;
        G[z.u].pb(mp(z.v, z.c));
        g[z.v].pb(mp(z.u, z.c));
        e.pb(z);
    }
    ll D[n+1], d[n+1], nD[n+1], nd[n+1];
    for(int i=0;i<n+1;i++) D[i]=inf;
    for(int i=0;i<n+1;i++) d[i]=inf;
    for(int i=0;i<n+1;i++) nD[i]=inf;
    for(int i=0;i<n+1;i++) nd[i]=inf;
    priority_queue<pll, vector<pll>, greater<pll> > pq;
    pq.push(mp(0, 1));
    while(!pq.empty()){
        pll cur=pq.top();
        pq.pop();
        if(D[cur.s]==inf) D[cur.s]=cur.f;
        else continue;
        for(pll u:G[cur.s]){
            if(D[u.f]!=inf) continue;
            pq.push(mp(cur.f+u.s, u.f));
        }
    }
    pq.push(mp(0, 1));
    while(!pq.empty()){
        pll cur=pq.top();
        pq.pop();
        if(d[cur.s]==inf) d[cur.s]=cur.f;
        else continue;
        for(pll u:g[cur.s]){
            if(d[u.f]!=inf) continue;
            pq.push(mp(cur.f+u.s, u.f));
        }
    }
    pq.push(mp(0, n));
    while(!pq.empty()){
        pll cur=pq.top();
        pq.pop();
        if(nD[cur.s]==inf) nD[cur.s]=cur.f;
        else continue;
        for(pll u:G[cur.s]){
            if(nD[u.f]!=inf) continue;
            pq.push(mp(cur.f+u.s, u.f));
        }
    }
    pq.push(mp(0, n));
    while(!pq.empty()){
        pll cur=pq.top();
        pq.pop();
        if(nd[cur.s]==inf) nd[cur.s]=cur.f;
        else continue;
        for(pll u:g[cur.s]){
            if(nd[u.f]!=inf) continue;
            pq.push(mp(cur.f+u.s, u.f));
        }
    }
    /*for(int i=1;i<=n;i++) cout << D[i] << " ";cout << endl;
    for(int i=1;i<=n;i++) cout << d[i] << " ";cout << endl;
    for(int i=1;i<=n;i++) cout << nD[i] << " ";cout << endl;
    for(int i=1;i<=n;i++) cout << nd[i] << " ";cout << endl;*/
    ll ans=inf;
    for(edge k:e){
        if(k.d+min(k.c+D[k.v]+nd[k.u], D[n])+min(k.c+nD[k.v]+d[k.u], nD[1])<ans) ans=k.d+min(k.c+D[k.v]+nd[k.u], D[n])+min(k.c+nD[k.v]+d[k.u], nD[1]);
    }
    if(ans==inf) cout << "-1\n";
    else cout << ans << endl;
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63