Submission #240320

#	Time	Username	Problem	Language	Result	Execution time	Memory
240320		arnold518	날다람쥐 (JOI14_ho_t4)	C++14	100 / 100	329 ms	24680 KiB

2014_ho_t4

#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;

int N, M, X, H[MAXN+10];
vector<pii> adj[MAXN+10];

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

ll dist[MAXN+10];
bool vis[MAXN+10];

int main()
{
    int i, j;

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

    priority_queue<Queue> PQ;
    PQ.push({1, X});
    while(!PQ.empty())
    {
        Queue now=PQ.top(); PQ.pop();
        if(vis[now.v]) continue;
        vis[now.v]=1; dist[now.v]=now.w;

        for(auto nxt : adj[now.v])
        {
            if(vis[nxt.first]) continue;
            PQ.push({nxt.first, min((ll)H[nxt.first], now.w-nxt.second)});
        }
    }

    if(!vis[N]) printf("-1\n");
    else printf("%lld\n", (ll)X+H[N]-2*dist[N]);
}

Compilation message (stderr)

2014_ho_t4.cpp: In function 'int main()':
2014_ho_t4.cpp:24:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
2014_ho_t4.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &M, &X);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:27:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d", &H[i]);
                         ~~~~~^~~~~~~~~~~~~
2014_ho_t4.cpp:31: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: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 50 / 50