Submission #711180

#	Time	Username	Problem	Language	Result	Execution time	Memory
711180		JJAnawat	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	327 ms	24544 KiB

commuter_pass

#include<bits/stdc++.h>

#define int long long
#define F first
#define S second

using namespace std;
using pi=pair<int,int>;

const int inf=1e18;
int n,m;
int S,T,U,V;
vector<pi> g[100005];

vector<int> dijk(int s){
    vector<int> dis(n+1,inf);
    priority_queue<pi,vector<pi>,greater<pi>> pq;
    dis[s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        auto [du,u]=pq.top();
        pq.pop();
        if(du!=dis[u])
            continue;
        for(auto [v,w]:g[u]){
            if(dis[v]>du+w){
                dis[v]=du+w;
                pq.push({du+w,v});
            }
        }
    }
    return dis;
}

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

    cin >> n >> m >> S >> T >> U >> V;
    for(int i=0,a,b,c;i<m;i++){
        cin >> a >> b >> c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    vector<int> s=dijk(S),t=dijk(T),u=dijk(U),v=dijk(V);
    vector<int> dpu(n+1,inf),dpv(n+1,inf);
    vector<pi> vec;
    for(int i=1;i<=n;i++){
        if(s[i]+t[i]==s[T])
            vec.push_back({s[i],i});
    }
    sort(vec.begin(),vec.end());
    int ans=inf;
    for(auto [si,i]:vec){
        dpu[i]=u[i];
        dpv[i]=v[i];
        for(auto [j,w]:g[i]){
            if(s[j]+w+t[i]==s[T]){
                dpu[i]=min(dpu[i],dpu[j]);
                dpv[i]=min(dpv[i],dpv[j]);
            }
        }
        ans=min(ans,dpu[i]+v[i]);
        ans=min(ans,dpv[i]+u[i]);
    }
    ans=min(ans,u[V]);
    cout << ans;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'std::vector<long long int> dijk(long long int)':
commuter_pass.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |         auto [du,u]=pq.top();
      |              ^
commuter_pass.cpp:25:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |         for(auto [v,w]:g[u]){
      |                  ^
commuter_pass.cpp: At global scope:
commuter_pass.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main(){
      | ^~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:54:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     for(auto [si,i]:vec){
      |              ^
commuter_pass.cpp:57:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         for(auto [j,w]:g[i]){
      |                  ^

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