#include<bits/stdc++.h>
using namespace std;
int n,m,k,q;
bool is_npp[100001];
vector<pair<int,int>> edges[100001];
vector<long long> sp(100001,INT_MAX);
vector<int> npp;
void dijkstra()
{
priority_queue<pair<long long,int>> q;
vector<long long> dist(n+1,INT_MAX);
for(int i=0;i<npp.size();i++)
{
q.push({0,npp[i]});
dist[npp[i]]=0;
sp[npp[i]]=0;
}
while(!q.empty())
{
int curr=q.top().second;
long long currDist=-q.top().first;
q.pop();
if(dist[curr]<currDist) continue;
for(auto edge:edges[curr])
{
int next=edge.first;
int weight=edge.second;
if(dist[curr]+weight<dist[next])
{
dist[next]=dist[curr]+weight;
sp[next]=min(sp[next],dist[next]);
q.push({-dist[next],next});
}
}
}
}
int dijkstra(int start,int finish)
{
priority_queue<pair<long long,int>> q;
vector<long long> away(n+1,0);
q.push({sp[start],start});
away[start]=sp[start];
while(!q.empty())
{
int curr=q.top().second;
long long currAway=q.top().first;
q.pop();
if(away[curr]>currAway) continue;
for(auto edge:edges[curr])
{
int next=edge.first;
long long len=sp[next];
if(away[next]<min(len,away[curr]))
{
away[next]=min(len,away[curr]);
q.push({away[next],next});
}
}
}
return away[finish];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
int ai,bi,wi;
for(int i=0;i<m;i++)
{
cin>>ai>>bi>>wi;
edges[ai].push_back({bi,wi});
edges[bi].push_back({ai,wi});
}
cin>>k;
for(int i=0;i<k;i++)
{
int npp1;
cin>>npp1;
is_npp[npp1]=true;
npp.push_back(npp1);
}
dijkstra();
cin>>q;
int si,ti;
for(int i=0;i<q;i++)
{
cin>>si>>ti;
if(is_npp[si]==true || is_npp[ti]==true) {printf("0\n");continue;}
printf("%lld\n",dijkstra(si,ti));
}
}
Compilation message
plan.cpp: In function 'void dijkstra()':
plan.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for(int i=0;i<npp.size();i++)
| ~^~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:89:20: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
89 | printf("%lld\n",dijkstra(si,ti));
| ~~~^ ~~~~~~~~~~~~~~~
| | |
| | int
| long long int
| %d
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
95 ms |
3676 KB |
Output is correct |
3 |
Correct |
78 ms |
3676 KB |
Output is correct |
4 |
Correct |
1 ms |
3420 KB |
Output is correct |
5 |
Correct |
67 ms |
3676 KB |
Output is correct |
6 |
Correct |
2 ms |
3672 KB |
Output is correct |
7 |
Correct |
1 ms |
3420 KB |
Output is correct |
8 |
Correct |
1 ms |
3420 KB |
Output is correct |
9 |
Correct |
27 ms |
3668 KB |
Output is correct |
10 |
Correct |
2 ms |
3676 KB |
Output is correct |
11 |
Correct |
30 ms |
3416 KB |
Output is correct |
12 |
Correct |
88 ms |
3672 KB |
Output is correct |
13 |
Correct |
13 ms |
3416 KB |
Output is correct |
14 |
Correct |
27 ms |
3672 KB |
Output is correct |
15 |
Correct |
27 ms |
3416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
95 ms |
3676 KB |
Output is correct |
3 |
Correct |
78 ms |
3676 KB |
Output is correct |
4 |
Correct |
1 ms |
3420 KB |
Output is correct |
5 |
Correct |
67 ms |
3676 KB |
Output is correct |
6 |
Correct |
2 ms |
3672 KB |
Output is correct |
7 |
Correct |
1 ms |
3420 KB |
Output is correct |
8 |
Correct |
1 ms |
3420 KB |
Output is correct |
9 |
Correct |
27 ms |
3668 KB |
Output is correct |
10 |
Correct |
2 ms |
3676 KB |
Output is correct |
11 |
Correct |
30 ms |
3416 KB |
Output is correct |
12 |
Correct |
88 ms |
3672 KB |
Output is correct |
13 |
Correct |
13 ms |
3416 KB |
Output is correct |
14 |
Correct |
27 ms |
3672 KB |
Output is correct |
15 |
Correct |
27 ms |
3416 KB |
Output is correct |
16 |
Execution timed out |
4034 ms |
8308 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
2 ms |
3416 KB |
Output is correct |
3 |
Correct |
1 ms |
3420 KB |
Output is correct |
4 |
Correct |
1 ms |
3420 KB |
Output is correct |
5 |
Correct |
1 ms |
3420 KB |
Output is correct |
6 |
Correct |
1 ms |
3420 KB |
Output is correct |
7 |
Correct |
1 ms |
3420 KB |
Output is correct |
8 |
Correct |
1 ms |
3420 KB |
Output is correct |
9 |
Correct |
1 ms |
3420 KB |
Output is correct |
10 |
Correct |
1 ms |
3420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
111 ms |
11988 KB |
Output is correct |
2 |
Correct |
226 ms |
20520 KB |
Output is correct |
3 |
Correct |
242 ms |
20424 KB |
Output is correct |
4 |
Correct |
30 ms |
7512 KB |
Output is correct |
5 |
Correct |
211 ms |
20440 KB |
Output is correct |
6 |
Correct |
244 ms |
20636 KB |
Output is correct |
7 |
Correct |
215 ms |
20684 KB |
Output is correct |
8 |
Correct |
210 ms |
20488 KB |
Output is correct |
9 |
Correct |
205 ms |
20452 KB |
Output is correct |
10 |
Correct |
298 ms |
20516 KB |
Output is correct |
11 |
Correct |
252 ms |
20596 KB |
Output is correct |
12 |
Correct |
250 ms |
20676 KB |
Output is correct |
13 |
Correct |
246 ms |
20488 KB |
Output is correct |
14 |
Correct |
228 ms |
20544 KB |
Output is correct |
15 |
Correct |
214 ms |
24368 KB |
Output is correct |
16 |
Correct |
273 ms |
28596 KB |
Output is correct |
17 |
Correct |
226 ms |
28640 KB |
Output is correct |
18 |
Correct |
212 ms |
28700 KB |
Output is correct |
19 |
Correct |
34 ms |
9048 KB |
Output is correct |
20 |
Correct |
210 ms |
28704 KB |
Output is correct |
21 |
Correct |
207 ms |
29352 KB |
Output is correct |
22 |
Correct |
58 ms |
13504 KB |
Output is correct |
23 |
Correct |
55 ms |
9852 KB |
Output is correct |
24 |
Correct |
66 ms |
13484 KB |
Output is correct |
25 |
Correct |
55 ms |
13592 KB |
Output is correct |
26 |
Correct |
46 ms |
10056 KB |
Output is correct |
27 |
Correct |
31 ms |
9052 KB |
Output is correct |
28 |
Correct |
57 ms |
13652 KB |
Output is correct |
29 |
Correct |
31 ms |
9020 KB |
Output is correct |
30 |
Correct |
74 ms |
14100 KB |
Output is correct |
31 |
Correct |
32 ms |
9044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
95 ms |
3676 KB |
Output is correct |
3 |
Correct |
78 ms |
3676 KB |
Output is correct |
4 |
Correct |
1 ms |
3420 KB |
Output is correct |
5 |
Correct |
67 ms |
3676 KB |
Output is correct |
6 |
Correct |
2 ms |
3672 KB |
Output is correct |
7 |
Correct |
1 ms |
3420 KB |
Output is correct |
8 |
Correct |
1 ms |
3420 KB |
Output is correct |
9 |
Correct |
27 ms |
3668 KB |
Output is correct |
10 |
Correct |
2 ms |
3676 KB |
Output is correct |
11 |
Correct |
30 ms |
3416 KB |
Output is correct |
12 |
Correct |
88 ms |
3672 KB |
Output is correct |
13 |
Correct |
13 ms |
3416 KB |
Output is correct |
14 |
Correct |
27 ms |
3672 KB |
Output is correct |
15 |
Correct |
27 ms |
3416 KB |
Output is correct |
16 |
Execution timed out |
4034 ms |
8308 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |