#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
ll n, m, ans, a, q , dis[1009] , pa[1009] , o;
string x, y ;
map<string ,ll>mp ;
vector<pair<ll,ll>>v[1009];
set <pair<ll,ll>> ss;
bool vis [1009];
int main()
{
ios::sync_with_stdio;cin.tie();cout.tie();
cin >> n >> m;
ll j = 1 ;
for(int i = 0; i < m ; i++)
{
cin >> x >> y >> a ;
if(mp[x] == 0)
{
mp[x] = j ;
j++ ;
}
if(mp[y] == 0)
{
mp[y] = j ;
j++ ;
}
v[mp[x]].push_back({mp[y],a});
}
cin >> q ;
while(q--)
{
ss.clear() ;
for( int i = 1 ; i <= n ; i++)
{
dis[i] = 1e18 ;
vis[i] = 0 ;
}
cin >> x >> y ;
ss.insert({0,mp[x]});
dis[mp[x]] = 0 ;
while(!ss.empty())
{
pair<ll,ll>u = *ss.begin();
ss.erase(u) ;
ll node = u.second ;
if(vis[node]) continue ;
vis[node] = 1 ;
for(auto p : v[node])
{
ll k = p.first ;
ll h = p.second ;
if(dis[k] > dis[node] + h)
{
pa[k] = node ;
dis[k] = dis[node] + h ;
ss.insert({dis[k],k}) ;
}
}
}
if(dis[mp[y]] == 1e18 )
cout << "Roger" << endl ;
else
cout << dis[mp[y]] << endl ;
}
return 0;
}
/*
3 2
novak goat 1
goat simulator 3
2
novak simulator
simulator goat
*/
Compilation message
alias.cpp: In function 'int main()':
alias.cpp:17:10: warning: statement is a reference, not call, to function 'std::ios_base::sync_with_stdio' [-Waddress]
17 | ios::sync_with_stdio;cin.tie();cout.tie();
| ~~~~~^~~~~~~~~~~~~~~
alias.cpp:17:10: warning: statement has no effect [-Wunused-value]
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
328 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
26 ms |
340 KB |
Output is correct |
4 |
Correct |
40 ms |
468 KB |
Output is correct |
5 |
Correct |
6 ms |
468 KB |
Output is correct |
6 |
Correct |
6 ms |
468 KB |
Output is correct |
7 |
Correct |
9 ms |
472 KB |
Output is correct |