제출 #834651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834651		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	332 ms	29232 KiB

commuter_pass

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<long long, long long>

const int nmax = 5e5 + 5;
const int mod = 1e9 + 7;
const long long INF = 1e18;

using namespace std;

int n, m, S, T, U, V;
priority_queue<pii, vector<pii>, greater<pii>> q;

long long dp[nmax][4], f[nmax], ans = INF;
pii a[nmax];

vector<pii> adj[nmax];

void build(int S, int x)
{
    for(int i = 1; i <= n; ++i)
    	dp[i][x] = INF;

    dp[S][x] = 0;
    q.push({0, S});
    while(q.size())
    {
        int u = q.top().se;
        int lc = q.top().fi;
        q.pop();
        for(auto tmp : adj[u])
        {
        	int v = tmp.first;
        	long long w = tmp.second;
            if(dp[v][x] > dp[u][x] + w)
            {
                dp[v][x] = dp[u][x] + w;
                q.push({dp[v][x], v});
            }
        }
    }
}

void solve()
{
    ans = dp[V][1];
    //S
    for(int i = 1; i <= n; ++i)
        a[i] = {dp[i][0], i};
    sort(a + 1, a + n + 1);
    //U
    for(int i = 1; i <= n; ++i)
        f[i] = dp[i][2];
    for(int i = n; i >= 1; --i){
        int u = a[i].se;
        for(auto [v, w] : adj[u])
        {
            if(dp[u][0] + w == dp[v][0] && dp[v][0] + dp[v][3] == dp[T][0]){
                f[u] = min(f[u], f[v]);
            }
        }
    }
    for(int i = 1; i <= n; ++i)
        ans = min(ans, f[i] + dp[i][1]);
    for(int i = 1; i <= n; ++i)
    f[i] = dp[i][1];
     for(int i = n; i >= 1; --i){
        int u = a[i].se;
        for(auto [v, w] : adj[u]){
            if(dp[u][0] + w == dp[v][0] && dp[v][0] + dp[v][3] == dp[T][0]){
                f[u] = min(f[u], f[v]);
            }
        }
    }
    //dp[i][2] = dp[i][u]
    for(int i = 1; i <= n; ++i) ans = min(ans, f[i] + dp[i][2]);
    cout << ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> S >> T >> U >> V;
    for(int i = 1; i <= m; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    build(S, 0);
    build(U, 1);
    build(V, 2);
    build(T, 3);
    solve();
}

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

commuter_pass.cpp: In function 'void build(int, int)':
commuter_pass.cpp:30:13: warning: unused variable 'lc' [-Wunused-variable]
   30 |         int lc = q.top().fi;
      |             ^~

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