#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>graph[1001000];
string s[1001000];
string c[1010000];
const int inf=1e17;
int w[1001000];
map<string ,int>mm;
vector<string>v;
map<string ,int>vi;
int dst[1010][1010];
int vstd[1010][1010];
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>s[i]>>c[i];
cin>>w[i];
if(!vi[s[i]])
{
vi[s[i]]=1;
v.push_back(s[i]);
}
if(!vi[c[i]])
{
vi[c[i]]=1;
v.push_back(c[i]);
}
}
for(int i=0;i<v.size();i++)
{
mm[v[i]]=i+1;
}
for(int i=0;i<m;i++)
{
graph[mm[s[i]]].push_back({mm[c[i]],w[i]});
}
for(int g=1;g<=n;g++){
priority_queue<pair<int,int>>pq;
pq.push({-0,g});
for(int i=1;i<=n;i++)
dst[g][i]=inf;
dst[g][g]=0;
while(!pq.empty())
{// cout<<endl;
int dist = -pq.top().first;//because we pushed it with minus distance
int node = pq.top().second;
pq.pop();
if(vstd[g][node])
continue;
vstd[g][node] = 1;
for(auto u:graph[node])
{
int new_distance = dist + u.second;//distance of new node = distance of this node + weight
if(new_distance<dst[g][u.first])
{
pq.push({-new_distance,u.first});
dst[g][u.first] = new_distance;
}
}
}
}
int u;
cin>>u;
while(u--)
{
string s,c;
cin>>s>>c;
if(dst[mm[s]][mm[c]]!=inf)
{
cout<<dst[mm[s]][mm[c]]<<endl;
}
else cout<<"Roger"<<endl;
}
}
Compilation message
alias.cpp:7:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
7 | const int inf=1e17;
| ^~~~
alias.cpp: In function 'int main()':
alias.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
86712 KB |
Output is correct |
2 |
Correct |
46 ms |
86836 KB |
Output is correct |
3 |
Correct |
52 ms |
87236 KB |
Output is correct |
4 |
Correct |
58 ms |
87756 KB |
Output is correct |
5 |
Correct |
59 ms |
94092 KB |
Output is correct |
6 |
Correct |
55 ms |
94148 KB |
Output is correct |
7 |
Correct |
56 ms |
95072 KB |
Output is correct |