Submission #153918

#	Time	Username	Problem	Language	Result	Execution time	Memory
153918		mhy908	날다람쥐 (JOI14_ho_t4)	C++14	50 / 100	514 ms	47468 KiB

2014_ho_t4

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define llinf 8987654321987654321
#define inf 1987654321
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
int n, m;
LL x;
LL h[100010];
vector<pair<int, LL> > link[100010];
priority_queue<pair<LL, pair<int, LL> > > pq;
LL dijk[100010];
int main()
{
    scanf("%d %d %d", &n, &m, &x);
    for(int i=1; i<=n; i++)scanf("%lld", &h[i]);
    for(int i=1; i<=m; i++){
        int a, b;
        LL c;
        scanf("%d %d %lld", &a, &b, &c);
        link[a].pb({b, c});
        link[b].pb({a, c});
    }
    pq.push({0, {-1, -x}});
    for(int i=1; i<=n; i++)dijk[i]=llinf;
    while(!pq.empty()){
        int here=-pq.top().S.F;
        LL x=-pq.top().S.S;
        LL c=-pq.top().F;
        pq.pop();
        if(c>=dijk[here])continue;
        dijk[here]=c;
        for(int i=0; i<link[here].size(); i++){
            int next=link[here][i].F;
            if(h[here]<link[here][i].S)continue;
            if(x-link[here][i].S>h[link[here][i].F]){
                //printf("%lld %d %lld\n", c+x-h[link[here][i].F]+link[here][i].S, link[here][i].F, h[link[here][i].F]);
                pq.push({-(c+x-(h[link[here][i].F]+link[here][i].S)+link[here][i].S), {-link[here][i].F, -h[link[here][i].F]}});
            }
            else if(x>=link[here][i].S){
                //printf("%lld %d %lld\n", c+link[here][i].S, link[here][i].F, x-link[here][i].S);
                pq.push({-(c+link[here][i].S), {-link[here][i].F, -(x-link[here][i].S)}});
            }
            else{
                //printf("%lld %d %lld\n", c+link[here][i].S*2-x, link[here][i].F, 0ll);
                pq.push({-(c+link[here][i].S*2-x), {-link[here][i].F, 0ll}});
            }
        }
    }
    if(dijk[n]==llinf)printf("-1");
    else printf("%lld", dijk[n]+h[n]);
}

Compilation message (stderr)

2014_ho_t4.cpp: In function 'int main()':
2014_ho_t4.cpp:20:33: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'LL* {aka long long int*}' [-Wformat=]
     scanf("%d %d %d", &n, &m, &x);
                               ~~^
2014_ho_t4.cpp:38:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<link[here].size(); i++){
                      ~^~~~~~~~~~~~~~~~~~
2014_ho_t4.cpp:39:17: warning: unused variable 'next' [-Wunused-variable]
             int next=link[here][i].F;
                 ^~~~
2014_ho_t4.cpp:20: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:21:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=n; i++)scanf("%lld", &h[i]);
                            ~~~~~^~~~~~~~~~~~~~~
2014_ho_t4.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %lld", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 0 / 50