제출 #683568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683568		yogesh_sane	Commuter Pass (JOI18_commuter_pass)	C++17	24 / 100	102 ms	262144 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <climits>
#include <algorithm>
using namespace std;
long long const INF = 1e15;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("in.txt","r",stdin);
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;

    vector<vector<long long>>dist(n+1, vector<long long>(n+1, INF));
    for(int i = 1; i <= n; i++)
        dist[i][i] = 0;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = c;
        dist[b][a] = c;
    }    

    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
            }
        }
    }
    long long ans = dist[u][v];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(dist[s][i]+dist[i][j]+dist[j][t] == dist[s][t]){
                ans = min(ans, min({dist[i][u]+dist[j][v],
                                    dist[i][v]+dist[j][u],
                                    dist[i][u]+dist[i][v],
                                    dist[j][u]+dist[j][v]}));
            }
        }
    }
    cout << ans << '\n';
   return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 45