제출 #369383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
369383		phathnv	Olympic Bus (JOI20_ho_t4)	C++11	100 / 100	661 ms	5624 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 201;
const int M = 50001;
const ll INF = 1e10;

struct edge{
    int u, v, c, d, ind;
};

int n, m;
edge eds[M];
ll dist[N][N], f[2][M], minDist[N];
int trace[N][N];
vector <edge> adj[N];

void ReadInput(){
    cin >> n >> m;
    for(int i = 1; i <= 2 * n; i++)
        for(int j = 1; j <= 2 * n; j++)
            dist[i][j] = (i != j) * INF;
    for(int i = 1; i <= m; i++){
        cin >> eds[i].u >> eds[i].v >> eds[i].c >> eds[i].d;
        eds[i].ind = i;
    }
}

ll Dijkstra(int s, int t, int revInd = 0){
    for(int i = 1; i <= n; i++)
        minDist[i] = INF;
    typedef pair<int, int> data;
    priority_queue <data, vector<data>, greater<data>> pq;
    minDist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()){
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if (minDist[u] != d)
            continue;
        if (u == t)
            return minDist[u];
        for(auto e : adj[u])
            if (e.ind != revInd && minDist[e.v] > minDist[e.u] + e.c){
                minDist[e.v] = minDist[e.u] + e.c;
                pq.push({minDist[e.v], e.v});
            }
        if (eds[revInd].v == u && minDist[eds[revInd].u] > minDist[u] + eds[revInd].c){
            minDist[eds[revInd].u] = minDist[u] + eds[revInd].c;
            pq.push({minDist[eds[revInd].u], eds[revInd].u});
        }
    }
    return INF;
}

void Solve(){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            dist[i][j] = (i != j) * INF;
    for(int i = 1; i <= m; i++){
        if (dist[eds[i].u][eds[i].v] > eds[i].c){
            dist[eds[i].u][eds[i].v] = eds[i].c;
            trace[eds[i].u][eds[i].v] = i;
        }
        adj[eds[i].u].push_back(eds[i]);
    }

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if (dist[i][j] > dist[i][k] + dist[k][j]){
                    dist[i][j] = dist[i][k] + dist[k][j];
                    trace[i][j] = trace[i][k];
                }

    int s = 1, t = n;
    for(int num = 0; num < 2; num++){
        for(int i = 1; i <= m; i++)
            f[num][i] = min(dist[s][t], dist[s][eds[i].v] + eds[i].c + dist[eds[i].u][t]);
        if (dist[s][t] != INF){
            cerr << num << endl;
            int u = s;
            while (u != t){
                int ind = trace[u][t];
                f[num][ind] = Dijkstra(s, t, ind);
                u = eds[ind].v;
            }
        }
        swap(s, t);
    }

    ll ans = dist[1][n] + dist[n][1];
    for(int i = 1; i <= m; i++)
        ans = min(ans, f[0][i] + f[1][i] + eds[i].d);
    cout << (ans < INF? ans : -1);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ReadInput();
    Solve();
    return 0;
}

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