oj.uz

답안 #647369

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
647369 2022-10-02T10:15:45 Z ck_platypus Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 30 ms 5316 KB 
#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 1000000000000000
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 5316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -