oj.uz

답안 #391947

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391947 2021-04-20T08:34:06 Z Jarif_Rahman Alias (COCI21_alias) C++17
70 / 70
 8 ms 8356 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e18;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    int wr = 0;
    vector<vector<pair<int, ll>>> v(n);
    map<str, int> index;
    vector<vector<ll>> dis(n, vector<ll>(n, inf));
    for(int i = 0; i < m; i++){
        str sa, sb; ll w; cin >> sa >> sb >> w;
        if(index.find(sa) == index.end()) index[sa] = wr++;
        if(index.find(sb) == index.end()) index[sb] = wr++;
        int a = index[sa], b = index[sb];
        v[a].pb({b, w});
    }
    for(int nd = 0; nd < n; nd++){
        priority_queue<pair<ll, int>> pq;
        vector<bool> bl(n, 0);
        dis[nd][nd] = 0;
        pq.push({0, nd});
        while(!pq.empty()){
            int nd0 = pq.top().sc;
            pq.pop();
            if(bl[nd0]) continue;
            bl[nd0] = 1;
            for(auto [x, w]: v[nd0]) if(dis[nd][nd0]+w < dis[nd][x]){
                dis[nd][x] = dis[nd][nd0]+w;
                pq.push({-dis[nd][x], x});
            }
        }
    }
    int q; cin >> q;
    while(q--){
        str sa, sb; cin >> sa >> sb;
        int a = index[sa], b = index[sb];
        if(dis[a][b] >= inf) cout << "Roger\n";
        else cout << dis[a][b] << "\n";
    }
}

Subtask #1
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 7 ms 6732 KB Output is correct
6 Correct 7 ms 6732 KB Output is correct
7 Correct 8 ms 8356 KB Output is correct