Submission #668819

#	Time	Username	Problem	Language	Result	Execution time	Memory
668819		Darren0724	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	273 ms	22248 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
#define x first
#define y second
const int INF=1e18;
int n,m;
vector<vector<pair<int,int>>> adj;
vector<vector<int>> dp;
vector<vector<int>> dis1;
vector<bool> vis;
int ans=0;
void dijkstra(int s){
    vector<int> dis(n,INF);
    dis[s]=0;
    priority_queue<pair<int,int>> pq;
    pq.push({0,s});
    while(pq.size()){
        int a,b;tie(a,b)=pq.top();
        pq.pop();
        a=-a;
        if(dis[b]!=a){
            continue;
        }
        for(auto p:adj[b]){
            if(dis[p.x]>dis[b]+p.y){
                dis[p.x]=dis[b]+p.y;
                pq.push({-dis[p.x],p.x});
            }
        }
    }
    dis1.push_back(dis);
}
void dfs(int k){
    vis[k]=1;
    for(auto p:adj[k]){
        if(dis1[2][k]-dis1[2][p.x]==p.y){
            if(!vis[p.x]){
                dfs(p.x);
            }
            dp[0][k]=min(dp[0][k],dp[0][p.x]);
            dp[1][k]=min(dp[1][k],dp[1][p.x]);
        }
    }
    ans=min({ans,dp[1][k]+dis1[0][k],dis1[1][k]+dp[0][k]});
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int s,t,u,v;
    cin>>n>>m>>s>>t>>u>>v;
    s--;t--;u--;v--;
    adj.resize(n);
    for(int i=0;i<m;i++){
        int a,b,c;cin>>a>>b>>c;a--;b--;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    dijkstra(u);
    dijkstra(v);
    dijkstra(s);
    ans=dis1[0][v];
    dp.resize(2);
    dp[0]=dis1[0];
    dp[1]=dis1[1];
    vis.resize(n);
    dfs(t);
    cout<<ans<<endl;
    return 0;
}

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