KOI: Gas Station

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
typedef long long lli;
typedef pair<int, int> pii;
typedef pair<lli, int> pli;

const int N = 2500 + 5;

vector<pii> adj[N];
lli dist[N], mat[N][N];
int nVertex, cost[N], idx[N];
bool visited[N];

void Dijkstra(int st){
    for(int u = 1; u <= nVertex; ++u){
        mat[st][u] = 1e18;
        visited[u] = false;
    }
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    mat[st][st] = 0;
    pq.emplace(mat[st][st], st);
    while(!pq.empty()){
        int u = pq.top().s;
        pq.pop();
        if(visited[u]){
            continue;
        }
        visited[u] = true;
        for(pii nxt : adj[u]){
            int v = nxt.f;
            int w = nxt.s;
            w *= cost[st];
            if(!visited[v] && mat[st][u] + w < mat[st][v]){
                mat[st][v] = mat[st][u] + w;
                pq.emplace(mat[st][v], v);
            }
        }
    }
}

int main(){

    int nEdge;
    scanf("%d%d", &nVertex, &nEdge);
    for(int i = 1; i <= nVertex; ++i){
        scanf("%d", &cost[i]);
    }
    for(int i = 1; i <= nEdge; ++i){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    for(int u = 1; u <= nVertex; ++u){
        Dijkstra(u);
        dist[u] = 1e18;
        idx[u] = u;
    }
    dist[1] = 0;
    for(int i = 0; i < nVertex; ++i){
        lli mn = 1e18;
        int u = 0;
        for(int j = 1; j <= nVertex - i; ++j){
            if(dist[j] < mn){
                mn = dist[j];
                u = j;
            }
        }
        if(idx[u] == nVertex){
            cout << dist[u];
            return 0;
        }
        for(int v = 1; v <= nVertex - i; ++v){
            if(dist[u] + mat[idx[u]][idx[v]] < dist[v]){
                dist[v] = dist[u] + mat[idx[u]][idx[v]];
            }
        }
        swap(idx[u], idx[nVertex - i]);
        swap(dist[u], dist[nVertex - i]);
    }

    return 0;
}