답안 #494328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
494328	2021-12-15T06:34:13 Z	asandikci	Alias (COCI21_alias)	C++17	70 / 70	27 ms	460 KB

alias

#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

#	결과	실행 시간	메모리	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