Advertisement
mickypinata

KOI: Gas Station

Dec 15th, 2021
622
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define f first
  5. #define s second
  6. typedef long long lli;
  7. typedef pair<int, int> pii;
  8. typedef pair<lli, int> pli;
  9.  
  10. const int N = 2500 + 5;
  11.  
  12. vector<pii> adj[N];
  13. lli dist[N], mat[N][N];
  14. int nVertex, cost[N], idx[N];
  15. bool visited[N];
  16.  
  17. void Dijkstra(int st){
  18.     for(int u = 1; u <= nVertex; ++u){
  19.         mat[st][u] = 1e18;
  20.         visited[u] = false;
  21.     }
  22.     priority_queue<pli, vector<pli>, greater<pli>> pq;
  23.     mat[st][st] = 0;
  24.     pq.emplace(mat[st][st], st);
  25.     while(!pq.empty()){
  26.         int u = pq.top().s;
  27.         pq.pop();
  28.         if(visited[u]){
  29.             continue;
  30.         }
  31.         visited[u] = true;
  32.         for(pii nxt : adj[u]){
  33.             int v = nxt.f;
  34.             int w = nxt.s;
  35.             w *= cost[st];
  36.             if(!visited[v] && mat[st][u] + w < mat[st][v]){
  37.                 mat[st][v] = mat[st][u] + w;
  38.                 pq.emplace(mat[st][v], v);
  39.             }
  40.         }
  41.     }
  42. }
  43.  
  44. int main(){
  45.  
  46.     int nEdge;
  47.     scanf("%d%d", &nVertex, &nEdge);
  48.     for(int i = 1; i <= nVertex; ++i){
  49.         scanf("%d", &cost[i]);
  50.     }
  51.     for(int i = 1; i <= nEdge; ++i){
  52.         int u, v, w;
  53.         scanf("%d%d%d", &u, &v, &w);
  54.         adj[u].emplace_back(v, w);
  55.         adj[v].emplace_back(u, w);
  56.     }
  57.     for(int u = 1; u <= nVertex; ++u){
  58.         Dijkstra(u);
  59.         dist[u] = 1e18;
  60.         idx[u] = u;
  61.     }
  62.     dist[1] = 0;
  63.     for(int i = 0; i < nVertex; ++i){
  64.         lli mn = 1e18;
  65.         int u = 0;
  66.         for(int j = 1; j <= nVertex - i; ++j){
  67.             if(dist[j] < mn){
  68.                 mn = dist[j];
  69.                 u = j;
  70.             }
  71.         }
  72.         if(idx[u] == nVertex){
  73.             cout << dist[u];
  74.             return 0;
  75.         }
  76.         for(int v = 1; v <= nVertex - i; ++v){
  77.             if(dist[u] + mat[idx[u]][idx[v]] < dist[v]){
  78.                 dist[v] = dist[u] + mat[idx[u]][idx[v]];
  79.             }
  80.         }
  81.         swap(idx[u], idx[nVertex - i]);
  82.         swap(dist[u], dist[nVertex - i]);
  83.     }
  84.  
  85.     return 0;
  86. }
  87.  
Advertisement
RAW Paste Data Copied
Advertisement