#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
using namespace std;
const int maxn=1005;
const int oo=1e18;
int tam=0;
map<string,int> id;
vector<pair<int,int>> e[maxn];
long long memo[maxn];
int getid(string x)
{
if(id.find(x)==id.end())
id[x]=++tam;
return id[x];
}
void dijkstra(int x)
{
priority_queue<pair<long long,int>> pq;
memo[x]=0;
pq.emplace(0,x);
while(!pq.empty())
{
auto [dd,y]=pq.top();
pq.pop();
if(memo[y]!=-dd)
continue;
for(auto [v,c]:e[y])
{
if(memo[v]>memo[y]+c)
{
memo[v]=memo[y]+c;
pq.emplace(-memo[v],v);
}
}
}
return;
}
int main()
{
faster
//freopen("ALIAS.INP", "r", stdin);
//freopen("ALIAS.OUT", "w", stdout);
int n,m,q;
cin >> n >> m;
for(int i=1;i<=m;i++)
{
string a,b;
int c;
cin >> a >> b >> c;
e[getid(a)].emplace_back(getid(b),c);
}
cin>>q;
while(q--)
{
string a,b;
cin >> a >> b;
for(int i=1;i<=n;i++)
memo[i]=oo;
int x, y;
x=getid(a);
y=getid(b);
dijkstra(x);
if(memo[y]==oo)
cout<<"Roger" << endl;
else
cout<< memo[y]<< endl;
}
return 0;
}
Compilation message
alias.cpp:7:14: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
7 | const int oo=1e18;
| ^~~~
alias.cpp: In function 'void dijkstra(int)':
alias.cpp:26:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
26 | auto [dd,y]=pq.top();
| ^
alias.cpp:30:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
30 | for(auto [v,c]:e[y])
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
18 ms |
332 KB |
Output is correct |
| 4 |
Correct |
26 ms |
464 KB |
Output is correct |
| 5 |
Correct |
6 ms |
460 KB |
Output is correct |
| 6 |
Correct |
6 ms |
460 KB |
Output is correct |
| 7 |
Correct |
6 ms |
460 KB |
Output is correct |
