제출 #173022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
173022		arnold518	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	880 ms	37072 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const ll INF = 1e18;

int N, M, S, T, U, V;
ll DU[MAXN+10], DV[MAXN+10], DS[MAXN+10], DT[MAXN+10], dp1[MAXN+10][2], dp2[MAXN+10][2];
vector<pll> adj[MAXN+10];
vector<int> adj2[MAXN+10], adj3[MAXN+10];

struct Queue
{
    ll v, w;
    bool operator < (const Queue& p) const { return w>p.w; }
};

void dijk(int s, ll* D)
{
    int i, j;
    for(i=1; i<=N; i++) D[i]=INF;
    priority_queue<Queue> PQ;
    PQ.push({s, 0});
    while(!PQ.empty())
    {
        Queue T=PQ.top(); PQ.pop();
        if(D[T.v]<=T.w) continue;
        D[T.v]=T.w;

        for(pii nxt : adj[T.v])
        {
            PQ.push({nxt.first, nxt.second+T.w});
        }
    }
}

bool vis[MAXN+10];
vector<int> order;
void dfs(int now, vector<int> *adj0)
{
    vis[now]=true;
    for(int nxt : adj0[now]) if(!vis[nxt]) dfs(nxt, adj0);
    order.push_back(now);
}

int main()
{
    int i, j;

    scanf("%d%d%d%d%d%d", &N, &M, &S, &T, &U, &V);
    for(i=1; i<=M; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dijk(U, DU); dijk(V, DV); dijk(S, DS); dijk(T, DT);
    for(i=1; i<=N; i++) for(pll nxt : adj[i]) if(DS[i]+nxt.second==DS[nxt.first]) adj2[i].push_back(nxt.first);
    for(i=1; i<=N; i++) for(pll nxt : adj[i]) if(DT[i]+nxt.second==DT[nxt.first]) adj3[i].push_back(nxt.first);

    memset(vis, 0, sizeof(vis)); order.clear();
    dfs(S, adj2);
    reverse(order.begin(), order.end());

    for(i=1; i<=N; i++) dp1[i][0]=dp1[i][1]=dp2[i][0]=dp2[i][1]=1e17;

    for(int now : order)
    {
        dp1[now][0]=min(dp1[now][0], DU[now]);
        dp1[now][1]=min(dp1[now][1], DV[now]);
        for(int nxt : adj2[now])
        {
            dp1[nxt][0]=min(dp1[nxt][0], dp1[now][0]);
            dp1[nxt][1]=min(dp1[nxt][1], dp1[now][1]);
        }
    }

    memset(vis, 0, sizeof(vis)); order.clear();
    dfs(T, adj3);
    reverse(order.begin(), order.end());

    for(int now : order)
    {
        dp2[now][0]=min(dp2[now][0], DU[now]);
        dp2[now][1]=min(dp2[now][1], DV[now]);
        for(int nxt : adj2[now])
        {
            dp2[nxt][0]=min(dp2[nxt][0], dp2[now][0]);
            dp2[nxt][1]=min(dp2[nxt][1], dp2[now][1]);
        }
    }

    ll ans=1e17;
    for(i=1; i<=N; i++) if(DS[i]+DT[i]==DS[T])
    {
        ans=min(ans, dp1[i][0]+dp2[i][1]);
        ans=min(ans, dp1[i][1]+dp2[i][0]);
    }
    printf("%lld", ans);
}

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

commuter_pass.cpp: In function 'void dijk(int, ll*)':
commuter_pass.cpp:24:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:52:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
commuter_pass.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d%d", &N, &M, &S, &T, &U, &V);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &u, &v, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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