Submission #471662

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
471662	2021-09-10T08:27:14 Z	LeeRise	Alias (COCI21_alias)	C++14	70 / 70	25 ms	916 KB

alias

# 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++){
      |                           ~^~~~~~~~~~~

Subtask #1

70.0 / 70.0

#	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