#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e18;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
int wr = 0;
vector<vector<pair<int, ll>>> v(n);
map<str, int> index;
vector<vector<ll>> dis(n, vector<ll>(n, inf));
for(int i = 0; i < m; i++){
str sa, sb; ll w; cin >> sa >> sb >> w;
if(index.find(sa) == index.end()) index[sa] = wr++;
if(index.find(sb) == index.end()) index[sb] = wr++;
int a = index[sa], b = index[sb];
v[a].pb({b, w});
}
for(int nd = 0; nd < n; nd++){
priority_queue<pair<ll, int>> pq;
vector<bool> bl(n, 0);
dis[nd][nd] = 0;
pq.push({0, nd});
while(!pq.empty()){
int nd0 = pq.top().sc;
pq.pop();
if(bl[nd0]) continue;
bl[nd0] = 1;
for(auto [x, w]: v[nd0]) if(dis[nd][nd0]+w < dis[nd][x]){
dis[nd][x] = dis[nd][nd0]+w;
pq.push({-dis[nd][x], x});
}
}
}
int q; cin >> q;
while(q--){
str sa, sb; cin >> sa >> sb;
int a = index[sa], b = index[sb];
if(dis[a][b] >= inf) cout << "Roger\n";
else cout << dis[a][b] << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
6 ms |
460 KB |
Output is correct |
| 5 |
Correct |
7 ms |
6732 KB |
Output is correct |
| 6 |
Correct |
7 ms |
6732 KB |
Output is correct |
| 7 |
Correct |
8 ms |
8356 KB |
Output is correct |
