Cod sursa(job #3284833)

Utilizator Vlad_Popescu123Popescu Vlad Vlad_Popescu123 Data 12 martie 2025 11:16:39
Problema Ubuntzei Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
#include <queue>
#define int long long
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");

int n,m,k;
vector<pair<int,int>> v[10001];
priority_queue<int, vector<int>, greater<int>> ubu;
//vector<int> ubu;

int dijkstra(int start, int dest){
    vector<int> dist(n+2, INT_MAX);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    dist[start] = 0;
    pq.push({0, start});
    
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        for(auto x : v[u]){
            int b = x.first;
            int weight = x.second;
            if(dist[b] > dist[u] + weight){
                dist[b] = dist[u] + weight;
                pq.push({dist[b], b});
            }
        }
    }
    
    return dist[dest];
}

signed main()
{
    f >> n >> m >> k;
    for(int i = 1; i<=k; i++){
        int x;
        f >> x;
        ubu.push(x);
    }
    
    for(int i = 1; i<=m; i++){
        int a,b,c; 
        f >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    
    int l = 0, start = 1;
    while(!ubu.empty()){
        int x = ubu.top();
        ubu.pop();
        l += dijkstra(start, x);
        start = x;
    }
    
    // for(int x : ubu){
    //     l += dijkstra(start, x);
    //     start = x;
    // }
    
    l+= dijkstra(start, n);
    g << l;
    
    
}