Submission #378520

#	Time	Username	Problem	Language	Result	Execution time	Memory
378520		daniel920712	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4050 ms	36956 KiB

plan

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <utility>

using namespace std;
vector < pair < int , int > > Next[200005];
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > dij;
priority_queue < pair < int , int > , vector < pair < int , int > > , less < pair < int , int > > > dij2;
int small[200005];
bool have[200005]={0};
int main()
{
    int N,M,K,Q,i,j,k,a,b,c,d,t;
    scanf("%d %d",&N,&M);
    for(i=0;i<M;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        Next[a].push_back(make_pair(b,c));
        Next[b].push_back(make_pair(a,c));
    }
    scanf("%d",&K);
    while(K--)
    {
        scanf("%d",&t);
        dij.push(make_pair(0,t));
    }
    while(!dij.empty())
    {
        a=dij.top().second;
        b=dij.top().first;
        dij.pop();
        if(have[a]) continue;
        //printf("%d %d\n",a,b);
        have[a]=1;
        small[a]=b;
        for(auto i:Next[a]) dij.push(make_pair(b+i.second,i.first));
    }
    scanf("%d",&Q);
    while(Q--)
    {
        scanf("%d %d",&c,&d);
        for(i=1;i<=N;i++) have[i]=0;
        dij2.push(make_pair(small[c],c));
        while(!dij2.empty())
        {
            a=dij2.top().second;
            b=dij2.top().first;
            dij2.pop();
            if(have[a]) continue;
            //printf("%d %d\n",a,b);
            if(a==d)
            {
                printf("%d\n",b);
                break;
            }
            have[a]=1;
            //small[a]=b;
            for(auto i:Next[a]) dij2.push(make_pair(min(b,small[i.first]),i.first));
        }
        while(!dij2.empty()) dij2.pop();
    }
    return 0;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:16:19: warning: unused variable 'j' [-Wunused-variable]
   16 |     int N,M,K,Q,i,j,k,a,b,c,d,t;
      |                   ^
plan.cpp:16:21: warning: unused variable 'k' [-Wunused-variable]
   16 |     int N,M,K,Q,i,j,k,a,b,c,d,t;
      |                     ^
plan.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
plan.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |         scanf("%d %d %d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
plan.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |     scanf("%d",&K);
      |     ~~~~~^~~~~~~~~
plan.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~
plan.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
plan.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |         scanf("%d %d",&c,&d);
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46