Submission #601270

#	Time	Username	Problem	Language	Result	Execution time	Memory
601270		ziduo	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	297 ms	23048 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define E '\n'
#define name "main"
#define X first
#define Y second
#define ii pair<int,int>
#define int ll
const int N = 1e5;
const ll oo = 1e18+19;
vector<ii> adj[N+13];
int numNode, numEdge;
ll dist[3][N+13];
ll dp[3][N+13];
int id[N+13];
int S,T,U,V;
 
bool minimize(ll &x, ll y){
    return x > y ? x = y,1 : 0;
}
void dijkstra(int start,ll d[]){
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    for (int i=1; i <= numNode ; ++i)
        d[i] = oo;
    pq.push({0,start});
    d[start] = 0;
    while (pq.size()){
        ii t = pq.top();
        pq . pop();
        int du = t.X;
        int u = t.Y;
        if (du != d[u]) continue;
 
        for (ii e: adj[u]){
            int v = e.Y;
            int uv = e.X;
            if (minimize(d[v],d[u] + uv))
                pq.push({d[v],v});
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout .tie(0);
//    freopen(name".inp","r",stdin); freopen(name".out","w",stdout);
    cin >> numNode >> numEdge;
    cin >> S >> T >> U >> V;
    for (int i=1; i <= numEdge; ++i){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].push_back({w,v});
        adj[v].push_back({w,u});
    }
    dijkstra(S,dist[2]);
    dijkstra(U,dist[0]);
    dijkstra(V,dist[1]);
    for (int i=1; i <= numNode; ++i)
        id[i] = i;
    sort(id+1,id+1+numNode,[&](int x,int y){
        return dist[2][x] < dist[2][y];
    });
    for (int i=1; i <= numNode; ++i){
        int u = id[i];
        dp[0][u] = dist[0][u];
        dp[1][u] = dist[1][u];
        dp[2][u] = dist[0][u] + dist[1][u];
 
        for (ii e: adj[u]){
            int v = e.Y;
            if (dist[2][v] + e.X > dist[2][u]) continue;
            for (int k=0 ; k < 3; ++k)
                minimize(dp[k][u],dp[k][v]);
        }
        minimize(dp[2][u],min(dp[0][u] + dist[1][u],dp[1][u] + dist[0][u]));
    }
    cout << min(dp[2][T],dist[0][V]);
    return 0;
}

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