#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 1010, M = 1e5+10, F = 2147483646, K = 20;
ll mx = 1e18;
int n, m, cur=1;
ll w, dp[N][N];
vector<pair<int, ll>> g[N];
map<string, int> ms;
void dijkstra(int v){
for(int i = 1; i <= n; ++i){
dp[v][i] = mx;
}
dp[v][v] = 0;
priority_queue<pair<ll, int>> q;
q.push({0, v});
vector<bool> visited(n + 5, 0);
while(!q.empty()){
int x = q.top().second;
q.pop();
if(visited[x]) continue;
visited[x] = 1;
for(auto y: g[x]){
if(dp[v][y.first] > dp[v][x] + y.second){
dp[v][y.first] = dp[v][x] + y.second;
q.push({-dp[v][y.first], y.first});
}
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n >> m;
for(int i = 0; i < m; i++){
string s, s1;
cin >> s >> s1 >> w;
if(ms[s] == 0) ms[s] = cur++;
if(ms[s1] == 0) ms[s1] = cur++;
g[ms[s]].pb({ms[s1], w});
}
for(int i = 1; i <= n; ++i){
dijkstra(i);
}
int q;
cin >> q;
while(q--){
string s, s1;
cin >> s >> s1;
ll ans = dp[ms[s]][ms[s1]];
if(ans == mx) cout << "Roger\n";
else cout << ans << '\n';
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
588 KB |
Output is correct |
| 4 |
Correct |
5 ms |
980 KB |
Output is correct |
| 5 |
Correct |
6 ms |
7500 KB |
Output is correct |
| 6 |
Correct |
6 ms |
7500 KB |
Output is correct |
| 7 |
Correct |
7 ms |
8396 KB |
Output is correct |
