#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define mp make_pair
#define vi vector<int>
#define pi pair<int ,int>
#define vpi vector<pair<int, int>>
#define vvi vector<vector<int>>
#define pqd priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
const int mod = 1e9+7;
#define ll long long
//PROGRAM
int main(){
// fastio
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// fastio
int n, e, q; cin >> n >> e >> q;
vpi a[n+1];
for (int i = 1; i <= e; i++)
{
int x, y, c; cin >> x >> y >> c;
a[x].pb({y, c});
a[y].pb({x, c});
}
priority_queue<pi, vpi> pq;
vi d(n+1, -1);
vi vis(n+1);
int s = 1; // 1 is the source
pq.push(mp(0, s)); // push source in the queue
d[1] = 0;
while(!pq.empty())
{
pi c = pq.top(); pq.pop();
if (vis[c.second]) continue;
vis[c.second] = true;
for (auto x : a[c.second])
{
if (vis[x.first]) continue;
if (c.second == 1)
{
d[x.first] = x.second;
pq.push({x.second, x.first});
continue;
}
if (min(c.first, x.second) > d[x.first])
{
d[x.first] = min(c.first, x.second);
pq.push({d[x.first], x.first});
}
}
}
while(q--)
{
int x; cin >> x;
cout << d[x] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
3388 KB |
Output is correct |
| 2 |
Correct |
22 ms |
2952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2112 ms |
104924 KB |
Output is correct |
| 2 |
Correct |
3056 ms |
166128 KB |
Output is correct |
