제출 #235970

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235970		Autoratch	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	2096 ms	18928 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define pii pair<long long,int> 

const int N = 1e5 + 1;

int n,m,s,t,u,v;
vector<pair<int,int> > adj[N];
long long dist[3][N];
bool visited[N];
priority_queue<pii,vector<pii>,greater<pii> > q;
long long ans = LLONG_MAX;

void dijk(int x,long long (&dist)[N])
{
    for(int i = 1;i <= n;i++) dist[i] = LLONG_MAX,visited[i] = false;
    dist[x] = 0;
    q.push({0,x});
    while(!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if(visited[u]) continue;
        visited[u] = true;
        for(auto [w,v] : adj[u]) if(dist[u]+w<dist[v])
        {
            dist[v] = dist[u]+w;
            q.push({dist[v],v});
        }
    }
}

void solve(int x,long long du,long long dv)
{
    ans = min(ans,du+dv);
    for(auto [w,v] : adj[x]) if(dist[0][v]+w==dist[0][x]) solve(v,min(du,dist[1][v]),min(dv,dist[2][v]));
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 0;i < m;i++)
    {
        int a,b,d;
        cin >> a >> b >> d;
        adj[a].push_back({d,b});
        adj[b].push_back({d,a});
    }
    dijk(s,dist[0]);
    dijk(u,dist[1]);
    dijk(v,dist[2]);
    solve(t,dist[1][t],dist[2][t]);
    cout << min(ans,dist[1][v]);
}

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

commuter_pass.cpp: In function 'void dijk(int, long long int (&)[100001])':
commuter_pass.cpp:25:18: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         for(auto [w,v] : adj[u]) if(dist[u]+w<dist[v])
                  ^
commuter_pass.cpp: In function 'void solve(int, long long int, long long int)':
commuter_pass.cpp:36:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [w,v] : adj[x]) if(dist[0][v]+w==dist[0][x]) solve(v,min(du,dist[1][v]),min(dv,dist[2][v]));
              ^

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