제출 #1158947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158947		dombly	Commuter Pass (JOI18_commuter_pass)	C++20	24 / 100	37 ms	3652 KiB

commuter_pass

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define int long long
using namespace std;
const int N = 300 + 10;
const int inf = 1e15;
const int mod = 998244353;

int n,m,s,t,u,v;
vector<pair<int,int>> g[N];

vector<int> Dijkstra(int src) {
    vector<int> Dist(n + 1,inf);
    Dist[src] = 0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    pq.push({0,src});
    while(!pq.empty()) {
        int dst = pq.top().F,node = pq.top().S;
        pq.pop();
        for(auto X : g[node]) {
            if(Dist[X.F] > dst + X.S) {
                Dist[X.F] = dst + X.S;
                pq.push({Dist[X.F],X.F});
            }
        }
    }
    return Dist;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 1; i <= m; i++) {
        int u,v,w;
        cin >> u >> v >> w;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    vector<int> S = Dijkstra(s);
    vector<int> T = Dijkstra(t);
    vector<int> U = Dijkstra(u);
    vector<int> V = Dijkstra(v);
    vector<vector<int>>Dist;
    Dist.resize(n + 1);
    for(int i = 1; i <= n; i++) Dist[i] = Dijkstra(i);
    int ans = U[v];
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(S[i] + T[j] + Dist[i][j] == S[t]) {
                ans = min(ans,U[i] + V[j]);
                ans = min(ans,U[j] + V[i]);
            }
        }
    }
    cout << ans;
    return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 45