Cod sursă (job #368977)

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

//Constants
const int N = 850;

//MACROS
#define pb push_back
#define fi first
#define se second
#define rep(i, begin, end) for (int i = (begin); i < (end); i++)
#define per(i, begin, end) for (int i = (begin) - 1; i >= (end); i--)
typedef long long LL;
typedef pair <int,int> PII;


vector < pair<int,int> > g[N];
int d[N], t, n, m, dp[N][N];
bool vis[N], foo[N][N];

int dive(int u) {
    vis[u] = 1;
    int ret = d[u];
    for (auto v : g[u]) if (!vis[v.first] && d[0] >= v.second) ret = max(ret,dive(v.first));
    return ret;
}

int ans2() {
    int ret = (1<<30);
    queue < pair<int,int> > q;
    rep(i,0,n) rep(j,0,n) dp[i][j] = (1<<30);
    dp[0][0] = 0;
    q.push({0,0});
    while (!q.empty()) {
        int u = q.front().first;
        int k = q.front().second;
        q.pop();
        foo[u][k] = false;
        for (auto v : g[u]) {
            if (d[k] >= v.second) {
                int kk = k;
                if (d[k] < d[v.first]) kk = v.first;
                if (dp[v.first][kk] > dp[u][k] + v.second) {
                    dp[v.first][kk] = dp[u][k] + v.second;
                    if (!foo[v.first][kk]) {
                        q.push({v.first,kk});
                        foo[v.first][kk] = true;
                    }
                }
            }
        }
    }
    rep(i,0,n) ret = min(ret, dp[n-1][i]);
    return ret;
}

int main() {
	//freopen("in.txt","r",stdin);
	freopen("dragoni2.in","r",stdin);
	freopen("dragoni2.out","w",stdout);

	cin >> t;
	cin >> n >> m;
	rep(i,0,n) cin >> d[i];
	rep(i,0,m) {
        int u, v, d;
        cin >> u >> v >> d;
        u--, v--;
        g[u].pb({v,d});
        g[v].pb({u,d});
	}
	if (t == 1) cout << dive(0);
	else cout << ans2();
}