Submission #746469

#	Time	Username	Problem	Language	Result	Execution time	Memory
746469		Azther0z	Commuter Pass (JOI18_commuter_pass)	C++11	31 / 100	268 ms	19412 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
vector<pair<int,int> > vec[100005];
ll dist1[100005],dist2[100005];

priority_queue<pair<ll,int> > pq;

int check[100005];
void solve(int now){

    check[now]=1;
    for(int i=0;i<vec[now].size();i++){
        int nxt=vec[now][i].f;
        ll nd=vec[now][i].s;
        if(dist1[now]-nd==dist1[nxt]&&check[nxt]==0){
            solve(nxt);
        }
    }

}
int main(){

    int n,m,st1,ed1,st2,ed2;
    scanf("%d %d %d %d %d %d",&n,&m,&st1,&ed1,&st2,&ed2);

    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        vec[x].push_back({y,z});
        vec[y].push_back({x,z});
    }
    for(int i=1;i<=n;i++){
        dist1[i]=1e15;
        dist2[i]=1e15;
    }
    dist1[st1]=0;
    dist2[st2]=0;

    pq.push({0,st1});

    while(pq.empty()==0){
        ll nowd=-pq.top().f;
        int now=pq.top().s;
        pq.pop();
        for(int i=0;i<vec[now].size();i++){
            ll nd=nowd+vec[now][i].s;
            int nxt=vec[now][i].f;
            if(nd<dist1[nxt]){
                dist1[nxt]=nd;
                pq.push({-nd,nxt});
            }
        }
    }
    solve(ed1);

    /*for(int i=1;i<=n;i++){
        printf("===%d %d\n",i,check[i]);
    */

    pq.push({0,st2});

    while(pq.empty()==0){
        ll nowd=-pq.top().f;
        int now=pq.top().s;
        pq.pop();
        for(int i=0;i<vec[now].size();i++){
            int nxt=vec[now][i].f;
            ll nd;
            if(check[now]==1&&check[nxt]==1){
                nd=nowd;
            }else{
                nd=nowd+vec[now][i].s;
            }
            if(nd<dist2[nxt]){
                dist2[nxt]=nd;
                pq.push({-nd,nxt});
            }
        }

    }
    printf("%lld",dist2[ed2]);

}

Compilation message (stderr)

commuter_pass.cpp: In function 'void solve(int)':
commuter_pass.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=0;i<vec[now].size();i++){
      |                 ~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int i=0;i<vec[now].size();i++){
      |                     ~^~~~~~~~~~~~~~~~
commuter_pass.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int i=0;i<vec[now].size();i++){
      |                     ~^~~~~~~~~~~~~~~~
commuter_pass.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d %d %d %d %d %d",&n,&m,&st1,&ed1,&st2,&ed2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d %d %d",&x,&y,&z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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