oj.uz

Submission #494328

# Submission time Handle Problem Language Result Execution time Memory
494328 2021-12-15T06:34:13 Z asandikci Alias (COCI21_alias) C++17
70 / 70
 27 ms 460 KB 
#include"iostream"
#include"vector"
#include"queue"
// #include"deque"
// #include"set"
#include"map"
#include"algorithm"
#include"cstring"
#define int long long
using namespace std;

const int maxn = 1005;
const int INF = 1e15;
map<string,int> mp;
vector<pair<int,int>> adj[maxn];
int shrt[maxn];
int aim;
int n;

void addedge(int a,int b,int w){
  adj[a].push_back({w,b});
}

void dijkstra(pair<int,int> cur){
  priority_queue<pair<int,int>, vector<pair<int,int>> , greater<pair<int,int>>> q;
  q.push(cur);
  while(!q.empty()){
    int val = q.top().second;
    int we  = q.top().first;
    q.pop();

    for(auto it : adj[val]){
      if(shrt[it.second]>shrt[val]+it.first){
        shrt[it.second]=shrt[val]+it.first;
        q.push({shrt[it.second],it.second});
      }
    }

  }
  if(shrt[aim]!=INF){
    cout << shrt[aim] << "\n";
  }
  else{
    cout << "Roger\n";
  }

}

void solve(){
  int m;
  cin >> n >> m;
  string str;
  string str2;
  int num=1;
  int w;
  for(int i=0;i<m;i++){
    cin >> str;
    if(mp[str]==0){mp[str]=num;num++;}
    cin >> str2;
    if(mp[str2]==0){mp[str2]=num;num++;}
    cin >> w;
    addedge(mp[str],mp[str2],w);
  }
  // for(auto it : mp){
  //   cout << it.first << " - " << it.second << "\n"; 
  // }

  int q;
  string cur,tmpaim;
  cin >> q;
  for(int i=0;i<q;i++){
    cin >> cur >> tmpaim;
    aim = mp[tmpaim];
    for(int i=1;i<=n;i++){shrt[i]=INF;}
    shrt[mp[cur]]=0;
    dijkstra({0,mp[cur]});
    // for(int i=1;i<=n;i++){
    //   cout << shrt[i] << " ";
    // }cout << "\n";
  }
}

signed main(){
  ios::sync_with_stdio(false); cin.tie(0);
  // freopen("","r",stdin);freopen("","w",stdout);
  int t=1;
  // cin >>t;
  for(int i=1;i<=t;i++){
    // cout << "Case " << i << ":\n";
    solve();
  }
}

Compilation message

alias.cpp: In function 'void dijkstra(std::pair<long long int, long long int>)':
alias.cpp:29:9: warning: unused variable 'we' [-Wunused-variable]
   29 |     int we  = q.top().first;
      |         ^~

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 16 ms 388 KB Output is correct
4 Correct 27 ms 392 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 3 ms 460 KB Output is correct