제출 #1104358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1104358		zephyrion	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	690 ms	7872 KiB

ho_t4

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

const int MAX_N = 210;
const int MAX_E = 50100;
const int INF = 1e9;

using Edge = pair<int, pair<int, int>>; 
using Graph = vector<vector<Edge>>;

Graph g, rg, ue;  
vector<int> d1, d2, rd1, rd2;  
int n, m, u, v, w, r;

int used[MAX_E];
int last[MAX_N];

vector<pair<pair<int, int>, pair<int, int>>> edges;  

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int blk = -1;

void dijkstra(int start, Graph &g, vector<int> &dist) {
    dist.resize(n + 1);
    fill(dist.begin(), dist.end(), INF);
    dist[start] = 0;
    pq.emplace(0, start);
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        int curr = top.second;
        int curr_dist = top.first;
        if (dist[curr] < curr_dist) continue;
        if (curr != start && blk == -1) used[last[curr]] = 1;
        for (const auto &edge : g[curr]) {
            int next = edge.first;
            int new_dist = curr_dist + edge.second.first;
            if (new_dist >= dist[next]) continue;
            if (edge.second.second == blk) continue;
            dist[next] = new_dist;
            last[next] = edge.second.second;
            pq.emplace(new_dist, next);
        }
    }
}

signed main() {
    
    cin >> n >> m;
    g.resize(n + 1);
    rg.resize(n + 1);
    ue.resize(n + 1);
    
    for (int i = 0; i < m; ++i) {
        cin >> u >> v >> w >> r;
        g[u].emplace_back(v, make_pair(w, i));
        rg[v].emplace_back(u, make_pair(w, i));
        edges.emplace_back(make_pair(u, v), make_pair(w, r));
    }
    
    dijkstra(1, g, d1);
    dijkstra(n, g, d2);
    dijkstra(1, rg, rd1);
    dijkstra(n, rg, rd2);
    
    int ans = d1[n] + d2[1];
    for (int i = 0; i < m; ++i) if (used[i]) {
        ue[edges[i].first.first].emplace_back(edges[i].first.second, make_pair(edges[i].second.first, i));
    }
    for (int i = 0; i < m; ++i) {
        if (used[i]) continue;
        
        int a = edges[i].first.first;
        int b = edges[i].first.second;
        int weight = edges[i].second.first;
        
        int forward = min(d1[n], d1[b] + weight + rd2[a]);
        int backward = min(d2[1], d2[b] + weight + rd1[a]);
        
        int total_weight = edges[i].second.second + forward + backward;
        
        ans = min(ans, total_weight);
    }
    for (int i = 0; i < m; ++i) {
        if (!used[i]) continue;
        
        int a = edges[i].first.first;
        int b = edges[i].first.second;
        int weight = edges[i].second.first;
        
        blk = i;
        vector<int> temp1, temp2;
        g[b].emplace_back(a, make_pair(weight, -INF));
        dijkstra(1, g, temp1);
        dijkstra(n, g, temp2);
        
        int total_weight = edges[i].second.second + temp1[n] + temp2[1];
        ans = min(ans, total_weight);
        g[b].pop_back();
    }
    cout << (ans >= INF ? -1 : ans);
    return 0;
}

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