#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
#define ii pair<int, int>
#define st first
#define nd second
#define maxn 100005
vector< ii > adj[maxn];
bool mark[maxn];
ii dist[maxn];
struct node
{
int u, d;
node(){}
node(int _u, int _d)
{
u = _u;
d = _d;
}
bool operator < (node other) const
{
return d> other.d;
}
};
int travel_plan(int n, int m, int R[][2], int *L, int k, int *P)
{
priority_queue< node > pq;
for(int i = 0; i< n; i++)
{
dist[i].st = dist[i].nd = 1e9;
pq.push(node(i, 1e9));
}
for(int i = 0; i< m; i++)
{
adj[R[i][0]].push_back(ii(R[i][1], L[i]));
adj[R[i][1]].push_back(ii(R[i][0], L[i]));
}
for(int i = 0; i< k; i++)
{
pq.push(node(P[i], 0));
dist[P[i]].st = dist[P[i]].nd = 0;
}
while(!pq.empty())
{
node x = pq.top();
pq.pop();
int u = x.u;
printf("popped %d with %d\n", u, x.d);
if(x.d != dist[u].nd) continue;
for(int i = 0; i< (int) adj[u].size(); i++)
{
ii k = adj[u][i];
int v = k.st, w = k.nd;
int nw = w+dist[u].nd;
if(nw < dist[v].st)
{
dist[v].nd = dist[v].st;
dist[v].st = nw;
pq.push(node(v, dist[v].nd));
}
else if(nw < dist[v].nd)
{
dist[v].nd = nw;
pq.push(node(v, dist[v].nd));
}
}
if(dist[0].nd != 1e9) printf("%d\n", dist[0].nd);
}
return dist[0].nd;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
