Cod sursă (job #369322)

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair< int , int > PII;
 
int pozr;
char buffer[1010];
FILE *fi, *fo;
             
char getch(){
    if( pozr == 1010 ){
        fread( buffer, 1010, 1, fi  );
        pozr = 0;
    }
    return buffer[ pozr++ ];
}
             
int scano(){
    int nr = 0;
    char ch = getch();
    while( isdigit(ch) == 0 )
        ch = getch();
    while( isdigit(ch) != 0 ){
        nr = nr * 10 + ch - '0';
        ch = getch();
    }
    return nr;
}
 
struct my{
    int weight;
    int drag;
    int node;
 
    my(int _weight = 0, int _drag = 0, int _node = 0) : weight(_weight), drag(_drag), node(_node){}
};
 
struct cmp{
    bool operator()(my a, my b){
        return a.weight > b.weight;
    }
};
 
int p, n, m, dr[810];
int dp[810][810];
bool st[810][810];
 
vector < PII > V[810];
priority_queue < my, vector < my >, cmp > H;
 
void Dijkstra(int x){
    my P(0, 1, 1);
    dp[1][1] = 0;
    st[1][1] = 1;
 
    H.push(P);
 
    while(H.size()){
        my P = H.top(); H.pop();
        int weight = P.weight;
        int node = P.node;
        int drag = P.drag;
 
        for (auto it : V[node]){
            if (it.second > dr[drag]) continue;
 
            if (dp[it.first][drag] > dp[node][drag] + it.second){
                dp[it.first][drag] = dp[node][drag] + it.second;
                my C(dp[it.first][drag], drag, it.first);
                H.push(C);
            }
        }
 
        if (!st[node][node]){
            st[node][node] = 1;
            dp[node][node] = weight;
            P = my(weight, node, node);
            H.push(P);
        }
    }
 
}
 
int main(){
    fi = fopen("dragoni2.in", "r");
    fo = fopen("dragoni2.out", "w");
 
    p = scano(); n = scano(); m = scano();
    for (int i = 1; i <= n; i++){
        dr[i] = scano();
        for (int j = 1; j <= n; j++)
            dp[i][j] = 2e9;
    }
 
    for (int i = 1, x, y, c; i <= m; i++){
        x = scano(), y = scano(), c = scano();
        V[x].push_back({y, c});
        V[y].push_back({x, c});
    }
 
    Dijkstra(1);
    int mn = 2e9, mx = dr[1];
 
    for (int j = 1; j <= n; j++){
        mn = min(mn, dp[n][j]);
        if (dp[j][1] != 2e9){
            mx = max(mx, dr[j]);
        }
    }
 
    fprintf(fo, "%d", (p == 1 ? mx : mn));
    return 0;
}