제출 #393624

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393624		79brue	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	153 ms	8388 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge{
    int u, v, idx; ll c, d;
    Edge(){}
    Edge(int u, int v, int idx, ll c, ll d): u(u), v(v), idx(idx), c(c), d(d){}

    bool operator==(const Edge &r)const{
        return idx == r.idx;
    }
};

int n, m;
vector<Edge> link[202];
vector<Edge> revLink[202];
Edge arr[50002];
ll ans = LLONG_MAX;

struct Dijkstra {
    int n;
    ll dist[202]; int prv[202], start, last;
    bool used[50002], chk[202];

    void init(int _n, int _start){
        n = _n, start = _start, last = n+1-start;
    }

    void run(){
        fill(dist+1, dist+n+1, 1e18);
        fill(chk+1, chk+n+1, false);
        fill(used+1, used+m+1, false);
        dist[start] = 0;

        while(1){
            int pnt = 0; ll pntD = 1e18;
            for(int i=1; i<=n; i++){
                if(!chk[i] && pntD > dist[i]) pntD = dist[i], pnt = i;
            }
            if(pnt == 0) break;

            chk[pnt] = 1;
            for(auto y: link[pnt]){
                int nxt = y.v;
                ll nxtCost = dist[pnt] + y.c;
                if(nxtCost < dist[nxt]){
                    dist[nxt] = nxtCost;
                    prv[nxt] = y.idx;
                }
            }
        }

        if(dist[last] == 1e18) return;
        int tmp = last;
        while(tmp != start){
            used[prv[tmp]] = 1;
            tmp = arr[prv[tmp]].u;
        }
    }
} dijk1, dijk2, dijktmp, dijk1rev, dijk2rev;

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        int u, v; ll c, d;
        scanf("%d %d %lld %lld", &u, &v, &c, &d);
        link[u].push_back(Edge(u, v, i, c, d));
        revLink[v].push_back(Edge(v, u, i, c, d));
        arr[i] = Edge(u, v, i, c, d);
    }

    dijk1.init(n, 1), dijk1rev.init(n, n), dijk2.init(n, n), dijk2rev.init(n, 1);
    dijk1.run(), dijk2.run();
    ans = dijk1.dist[n] + dijk2.dist[1];

    for(int i=1; i<=n; i++) revLink[i].swap(link[i]);
    for(int i=1; i<=m; i++) swap(arr[i].u, arr[i].v);
    dijk1rev.run();
    dijk2rev.run();
    for(int i=1; i<=n; i++) revLink[i].swap(link[i]);
    for(int i=1; i<=m; i++) swap(arr[i].u, arr[i].v);

    for(int i=1; i<=m; i++){
        ll ret = arr[i].d;
        if(!dijk1.used[i]) ret += min(dijk1.dist[n], dijk1.dist[arr[i].v] + dijk1rev.dist[arr[i].u] + arr[i].c);
        else{
            link[arr[i].u].erase(find(link[arr[i].u].begin(), link[arr[i].u].end(), arr[i]));
            swap(arr[i].u, arr[i].v);
            link[arr[i].u].push_back(arr[i]);

            dijktmp.init(n, 1);
            dijktmp.run();
            ret += dijktmp.dist[n];

            link[arr[i].u].erase(find(link[arr[i].u].begin(), link[arr[i].u].end(), arr[i]));
            swap(arr[i].u, arr[i].v);
            link[arr[i].u].push_back(arr[i]);
        }

        if(!dijk2.used[i]) ret += min(dijk2.dist[1], dijk2.dist[arr[i].v] + dijk2rev.dist[arr[i].u] + arr[i].c);
        else{
            link[arr[i].u].erase(find(link[arr[i].u].begin(), link[arr[i].u].end(), arr[i]));
            swap(arr[i].u, arr[i].v);
            link[arr[i].u].push_back(arr[i]);

            dijktmp.init(n, n);
            dijktmp.run();
            ret += dijktmp.dist[1];

            link[arr[i].u].erase(find(link[arr[i].u].begin(), link[arr[i].u].end(), arr[i]));
            swap(arr[i].u, arr[i].v);
            link[arr[i].u].push_back(arr[i]);
        }

        ans = min(ans, ret);
    }

    printf("%lld", ans > 1e17 ? -1 : ans);
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
ho_t4.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |         scanf("%d %d %lld %lld", &u, &v, &c, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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