Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.8 kB
1
Indexable
Never
#include<bits/stdc++.h>
#define PAIR pair<int,int>

using namespace std;
unsigned long long int ans = INT_MAX;
int N, S, E, T, v, u, w, B;
long long int dist_from_start[2005];
long long int dist_from_des[2005];
// N: spots in the mine
// S: start, E: exit, T: number of tunnels, B: number of bridges
// v & u: two neighbor spot, w: length between v and u
void AddEdge(vector <PAIR> adj[], int v, int u, int weight){
    adj[v].push_back({u, weight});
    adj[u].push_back({v, weight});
}
void dijkstra(vector<PAIR> Tunnel[], int N, int start){
    vector<bool> visited(N, false);
    priority_queue<PAIR, vector<PAIR>, greater<PAIR>> pq;
    pq.push({start, 0});
    dist_from_start[start] = 0;
    while(!pq.empty()){
        int cur = pq.top().first;
        pq.pop();
        if(visited[cur]) continue;
        visited[cur] = true;
        for(auto it: Tunnel[cur]){
            int v = it.first;
            int weight = it.second;
            if(dist_from_start[v] > dist_from_start[cur] + weight){
                dist_from_start[v] = dist_from_start[cur] + weight;
                pq.push({v, dist_from_start[v]});
            }
        }
    }
}
void dijkstra_inverse(vector<PAIR> Tunnel[], int N, int start){
    vector<bool> visited(N, false);
    priority_queue<PAIR, vector<PAIR>, greater<PAIR>> pq;
    pq.push({start, 0});
    dist_from_des[start] = 0;
    while(!pq.empty()){
        int cur = pq.top().first;
        pq.pop();
        if(visited[cur]) continue;
        visited[cur] = true;
        for(auto it: Tunnel[cur]){
            int v = it.first;
            int weight = it.second;
            if(dist_from_des[v] > dist_from_des[cur] + weight){
                dist_from_des[v] = dist_from_des[cur] + weight;
                pq.push({v, dist_from_des[v]});
            }
        }
    }
}
int main(void){
    cin >> N >> S >> E;
    vector <PAIR> Bridge[N], Tunnel[N];
    cin >> T;
    for(int i=0; i<N; i++) dist_from_start[i] = INT_MAX;
    for(int i=0; i<N; i++) dist_from_des[i] = INT_MAX;
    for(int i=0; i<T; i++){
        cin >> v >> u >> w;
        AddEdge(Tunnel, v-1, u-1, w);
    }
    cin >> B;
    for(int i=0; i<B; i++){
        cin >> v >> u >> w;
        AddEdge(Bridge, v-1, u-1, w);
    }
    dijkstra(Tunnel, N, S-1);
    dijkstra_inverse(Tunnel, N, E-1);
    for(int i=0; i<N; i++){
        for(auto it: Bridge[i]){
            int v = it.first;
            int weight = it.second;
            if(dist_from_start[E-1] > dist_from_start[i] + weight + dist_from_des[v])
                dist_from_start[E-1] = dist_from_start[i] + weight + dist_from_des[v];
        }
    }
    cout << dist_from_start[E-1] << endl;
    return 0;
}