#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
ll const big = 2000000000;
ll const ultrabig = 12000000000000;
ll const infinity = 1234567890123456;
ll edges[20007];
ll lastedgeindex[5007];
ll tempo[5007];
ll final[5007];
ll edgedecoder(ll edge, ll id)
{
if (id==0)
return edge/ultrabig;
if (id==2)
return edge%big;
return (edge/big)%6000;
}
ll startindex(ll lastedgeindex[5007], ll i)
{
if (i==0)
return 0;
return lastedgeindex[i-1]+1;
}
int main()
{
ll n, e, k;
cin >> n >> e >> k;
ll edgecount=0;
for (ll i=1; i<=k; i++)
{
ll votingbooth;
cin >> votingbooth;
votingbooth+=1;
edges[edgecount] = votingbooth*big;
edgecount++;
}
for (ll i=1; i<=e; i++)
{
ll ui, vi, ci;
cin >> ui >> vi >> ci;
ui+=1;
vi+=1;
edges[edgecount] = vi*ultrabig+ui*big+ci;
edgecount++;
}
sort(edges, edges+edgecount);
edges[edgecount]=-1;
/*for (ll i=0; i<edgecount; i++)
{
cout << edgedecoder(edges[i], 0) << ' ' << edgedecoder(edges[i], 1) << ' ' << edgedecoder(edges[i], 2) << '\n';
}*/
ll counter=0;
for (ll city=0; city<=n; city++)
{
while (edgedecoder(edges[counter], 0)==city)
{
counter++;
}
lastedgeindex[city]=counter-1;
}
for (ll i=0; i<=n; i++)
{
tempo[i]=infinity;
final[i]=infinity;
}
tempo[0]=0;
final[0]=0;
ll curr=0;
for (ll iteration=1; iteration<=n; iteration++)
{
for (ll edgetocheck=startindex(lastedgeindex, curr); edgetocheck<=lastedgeindex[curr]; edgetocheck++)
{
ll newcity=edgedecoder(edges[edgetocheck], 1);
ll travelcost=edgedecoder(edges[edgetocheck], 2);
if (final[newcity]==infinity)
{
tempo[newcity]=min(tempo[newcity], final[curr]+travelcost);
}
}
ll lowestcost=infinity;
ll bestindex=n+1;
for (ll city=1; city<=n; city++)
{
if (final[city]==infinity and tempo[city]<lowestcost)
{
lowestcost=tempo[city];
bestindex=city;
}
}
curr=bestindex;
final[bestindex]=lowestcost;
}
ll q;
cin >> q;
for (ll query=1; query<=q; query++)
{
ll start, p1, p2, p3, p4, p5;
cin >> start >> p1 >> p2 >> p3 >> p4 >> p5;
start+=1;
if (final[start]!=infinity)
cout << final[start] << '\n';
else
cout << "-1\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
468 KB |
Output is correct |
2 |
Correct |
39 ms |
340 KB |
Output is correct |
3 |
Correct |
35 ms |
504 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
468 KB |
Output is correct |
2 |
Correct |
39 ms |
340 KB |
Output is correct |
3 |
Correct |
35 ms |
504 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
38 ms |
468 KB |
Output is correct |
7 |
Correct |
34 ms |
340 KB |
Output is correct |
8 |
Correct |
36 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
468 KB |
Output is correct |
2 |
Correct |
39 ms |
340 KB |
Output is correct |
3 |
Correct |
35 ms |
504 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
38 ms |
468 KB |
Output is correct |
7 |
Correct |
34 ms |
340 KB |
Output is correct |
8 |
Correct |
36 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
284 KB |
Output is correct |
11 |
Correct |
36 ms |
520 KB |
Output is correct |
12 |
Correct |
34 ms |
440 KB |
Output is correct |
13 |
Correct |
49 ms |
480 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
468 KB |
Output is correct |
2 |
Correct |
39 ms |
340 KB |
Output is correct |
3 |
Correct |
35 ms |
504 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
39 ms |
484 KB |
Output is correct |
7 |
Correct |
40 ms |
340 KB |
Output is correct |
8 |
Correct |
38 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
468 KB |
Output is correct |
2 |
Correct |
39 ms |
340 KB |
Output is correct |
3 |
Correct |
35 ms |
504 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
38 ms |
468 KB |
Output is correct |
7 |
Correct |
34 ms |
340 KB |
Output is correct |
8 |
Correct |
36 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
284 KB |
Output is correct |
11 |
Correct |
39 ms |
484 KB |
Output is correct |
12 |
Correct |
40 ms |
340 KB |
Output is correct |
13 |
Correct |
38 ms |
504 KB |
Output is correct |
14 |
Incorrect |
41 ms |
484 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
38 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
468 KB |
Output is correct |
2 |
Correct |
39 ms |
340 KB |
Output is correct |
3 |
Correct |
35 ms |
504 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
38 ms |
468 KB |
Output is correct |
7 |
Correct |
34 ms |
340 KB |
Output is correct |
8 |
Correct |
36 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
284 KB |
Output is correct |
11 |
Correct |
36 ms |
520 KB |
Output is correct |
12 |
Correct |
34 ms |
440 KB |
Output is correct |
13 |
Correct |
49 ms |
480 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
39 ms |
484 KB |
Output is correct |
17 |
Correct |
40 ms |
340 KB |
Output is correct |
18 |
Correct |
38 ms |
504 KB |
Output is correct |
19 |
Incorrect |
41 ms |
484 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |