# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
471662 |
2021-09-10T08:27:14 Z |
LeeRise |
Alias (COCI21_alias) |
C++14 |
|
25 ms |
916 KB |
# include <bits/stdc++.h>
# define F first
# define S second
# define ps push
using namespace std;
int n,m;
int tt;
long long t;
string a,b;
vector<pair<int,long long>>g[10001];
priority_queue<pair<long long,long long>> q;
long long d[5001];
map<string,int>ma;
long long tg[2001];
pair<string,string>luu[2001];
void dijkstra(int s)
{
for (int i=0;i<=n;i++)
{
d[i]=99999999999999;
}
d[s]=0;
q.ps({0,s});
while (!q.empty())
{
int u=q.top().S;
long long du=-q.top().F;
q.pop();
if (d[u]<du) continue;
for (int i=0;i<g[u].size();i++)
{
int v=g[u][i].F;
long long l=g[u][i].S;
if (d[v]>du+l)
{
d[v]=du+l;
q.ps({-d[v],v});
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("Alias.inp","r",stdin);
//freopen("Alias.out","w",stdout);
cin>>n>>m;
vector<string>pre;
for (int i=1;i<=m;i++){
cin>>a>>b>>tg[i];
if (ma[a]==0){
pre.push_back(a);
}
if (ma[b]==0){
pre.push_back(b);
}
ma[a]++;
ma[b]++;
luu[i]={a,b};
}
for (int i=1;i<=m;i++){
int u=-1,v=-1;
for ( int j=0;j<pre.size();j++){
if (luu[i].F==pre[j]) {u=j;ma[luu[i].F]=u;}
if (luu[i].S==pre[j]) {v=j;ma[luu[i].S]=v;}
if (u!=-1&&v!=-1) break;
}
g[u].push_back({v,tg[i]});
}
cin>>tt;
while (tt--){
cin>>a>>b;
int u=ma[a];
int v=ma[b];
dijkstra(u);
if (d[v]==99999999999999) cout<<"Roger\n";
else
cout<<d[v]<<"\n";
}
}
Compilation message
alias.cpp: In function 'void dijkstra(int)':
alias.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i=0;i<g[u].size();i++)
| ~^~~~~~~~~~~~
alias.cpp: In function 'int main()':
alias.cpp:65:28: 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]
65 | for ( int j=0;j<pre.size();j++){
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
3 |
Correct |
17 ms |
776 KB |
Output is correct |
4 |
Correct |
25 ms |
792 KB |
Output is correct |
5 |
Correct |
9 ms |
844 KB |
Output is correct |
6 |
Correct |
9 ms |
916 KB |
Output is correct |
7 |
Correct |
12 ms |
844 KB |
Output is correct |