#include<bits/stdc++.h>
using namespace std;
vector<pair<int,long long>>g[1001];
bool used[1001];
long long dist[1001];
void dijkstra(int source)
{
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pq;
pq.push({0,source});
while(pq.size())
{
long long cost=pq.top().first;
int node=pq.top().second;
pq.pop();
if(used[node])continue;
used[node]=1;
dist[node]=cost;
for(pair<int,long long>go:g[node])
{
if(used[go.first])continue;
pq.push({go.second+cost,go.first});
}
}
}
int main()
{
int n,m;
cin>>n>>m;
set<string>s;
vector<pair<string,pair<string,long long>>>v;
for(int i=0;i<m;i++)
{
string a,b;
long long c;
cin>>a>>b>>c;
v.push_back({a,{b,c}});
s.insert(a);
s.insert(b);
}
map<string,int>mp1;
int ii=1;
for(string i:s)mp1[i]=ii,ii++;
for(pair<string,pair<string,long long>>i:v)
g[mp1[i.first]].push_back({mp1[i.second.first],i.second.second});
int q;
cin>>q;
while(q--)
{
for(int i=0;i<1001;i++)dist[i]=1000000000000000000,used[i]=0;
string s,e;
cin>>s>>e;
dijkstra(mp1[s]);
if(dist[mp1[e]]==1000000000000000000)cout<<"Roger"<<endl;
else cout<<dist[mp1[e]]<<endl;
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
49 ms |
604 KB |
Output is correct |
| 4 |
Correct |
46 ms |
604 KB |
Output is correct |
| 5 |
Correct |
5 ms |
860 KB |
Output is correct |
| 6 |
Correct |
7 ms |
856 KB |
Output is correct |
| 7 |
Correct |
5 ms |
860 KB |
Output is correct |
