Submission #956159

#	Time	Username	Problem	Language	Result	Execution time	Memory
956159		samvar_0907	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1088 ms	9040 KiB

ho_t4

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 201, M = 40001;
 
int n, m;
 
multiset<pair<int, int>> adj[N];
int c[M], d[M];
pair<int, int> edges[M];

vector<int> dijkstra(int source){
    vector<int> dist(n + 1, 1e15);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, source});
    dist[source] = 0;
    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        for (auto &n : adj[u]){
            if (dist[n.first] > d + c[n.second]){
                dist[n.first] = d + c[n.second];
                pq.push({dist[n.first], n.first});
            }
        }
    }
    return dist;
}

signed main(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        adj[i].clear();
    }

    for (int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v >> c[i] >> d[i];
        adj[u].insert({v, i});
        edges[i] = {u, v};
    }
    int ans = 1e15;
    for (int i = 0; i < m; ++i) {   // for each edge
        for (int bin_val = 0; bin_val < 2; ++bin_val) {  // binary value which is 0 or 1

            if (bin_val) {
                adj[edges[i].first].erase(adj[edges[i].first].find({edges[i].second, i}));
                adj[edges[i].second].insert({edges[i].first, i});
            }
            vector<int> start = dijkstra(1);  // from start
            vector<int> target = dijkstra(n);  // from target

            int ans_temp = d[i] * bin_val + start[n] + target[1];
            ans = min(ans, ans_temp);

            if (bin_val) {
                adj[edges[i].second].erase(adj[edges[i].second].find({edges[i].first, i}));
                adj[edges[i].first].insert({edges[i].second, i});
            }
        }
    }
    if (ans == (int)(1e15)) {
        cout << -1;
    }
    else{
        cout << ans;
    }
    return 0;
}   

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