#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
typedef pair<int, int> pii;
int vis[maxn], dist[maxn], dist2[maxn];
vector<pii> G[maxn];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
memset(dist, 0x3f3f3f3f, sizeof(dist));
memset(dist2, 0x3f3f3f3f, sizeof(dist));
for(int i = 0; i < M; i++)
{
int a = R[i][0], b = R[i][1];
G[a].push_back({L[i], b});
G[b].push_back({L[i], a});
}
// for(int i = 0; i < N; i++)
// for(auto u : G[i])
// cout << i << " " << u.second << " " << u.first << "\n";
priority_queue<pii, vector<pii>, greater<pii>> q;
for(int i = 0; i < K; i++)
{
dist[P[i]] = dist2[P[i]] = 0;
q.push({0, P[i]});
}
while(!q.empty())
{
auto a = q.top();
q.pop();
//cout << a.second << " \n";
if(vis[a.second]) continue;
vis[a.second] = true;
for(auto u : G[a.second])
{
if(dist[u.second] > dist2[a.second] + u.first)
{
dist2[u.second] = dist[u.second];
dist[u.second] = dist2[a.second] + u.first;
// CÓDIGO MÁGICO COMEÇA AQUI
if (dist2[u.second] != dist[u.second])
q.push({dist2[u.second], u.second});
// CÓDIGO MÁGICO TERMINA AQUI
}
else if(dist2[u.second] > dist2[a.second] + u.first)
{
dist2[u.second] = dist2[a.second] + u.first;
q.push({dist2[u.second], u.second});
}
}
}
return dist2[0];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3312 KB |
Output is correct |
| 3 |
Correct |
6 ms |
3584 KB |
Output is correct |
| 4 |
Correct |
6 ms |
3584 KB |
Output is correct |
| 5 |
Correct |
7 ms |
3584 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3456 KB |
Output is correct |
| 7 |
Correct |
6 ms |
3584 KB |
Output is correct |
| 8 |
Correct |
6 ms |
3584 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3312 KB |
Output is correct |
| 3 |
Correct |
6 ms |
3584 KB |
Output is correct |
| 4 |
Correct |
6 ms |
3584 KB |
Output is correct |
| 5 |
Correct |
7 ms |
3584 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3456 KB |
Output is correct |
| 7 |
Correct |
6 ms |
3584 KB |
Output is correct |
| 8 |
Correct |
6 ms |
3584 KB |
Output is correct |
| 9 |
Correct |
6 ms |
3712 KB |
Output is correct |
| 10 |
Correct |
6 ms |
3456 KB |
Output is correct |
| 11 |
Correct |
7 ms |
3584 KB |
Output is correct |
| 12 |
Correct |
10 ms |
3968 KB |
Output is correct |
| 13 |
Correct |
8 ms |
3968 KB |
Output is correct |
| 14 |
Correct |
5 ms |
3584 KB |
Output is correct |
| 15 |
Correct |
6 ms |
3584 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3312 KB |
Output is correct |
| 3 |
Correct |
6 ms |
3584 KB |
Output is correct |
| 4 |
Correct |
6 ms |
3584 KB |
Output is correct |
| 5 |
Correct |
7 ms |
3584 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3456 KB |
Output is correct |
| 7 |
Correct |
6 ms |
3584 KB |
Output is correct |
| 8 |
Correct |
6 ms |
3584 KB |
Output is correct |
| 9 |
Correct |
6 ms |
3712 KB |
Output is correct |
| 10 |
Correct |
6 ms |
3456 KB |
Output is correct |
| 11 |
Correct |
7 ms |
3584 KB |
Output is correct |
| 12 |
Correct |
10 ms |
3968 KB |
Output is correct |
| 13 |
Correct |
8 ms |
3968 KB |
Output is correct |
| 14 |
Correct |
5 ms |
3584 KB |
Output is correct |
| 15 |
Correct |
6 ms |
3584 KB |
Output is correct |
| 16 |
Correct |
737 ms |
58940 KB |
Output is correct |
| 17 |
Correct |
123 ms |
15300 KB |
Output is correct |
| 18 |
Correct |
159 ms |
16744 KB |
Output is correct |
| 19 |
Correct |
845 ms |
63496 KB |
Output is correct |
| 20 |
Correct |
357 ms |
50308 KB |
Output is correct |
| 21 |
Correct |
65 ms |
8696 KB |
Output is correct |
| 22 |
Correct |
346 ms |
46972 KB |
Output is correct |
