View Code of Problem 3830

#include <bits/stdc++.h>
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pI;
typedef vector<ll> vI;
const ll mod(1e9 + 7);
const ll INF(0x3f3f3f3f);
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a%mod; a = a * a%mod; }return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
// head

const int maxn(2e4+7);
int n, m, u, v, w;

int mapp[maxn][maxn], lenth[maxn];
bool visited[maxn];

void dijkstra(int nowPos) {
	mem(visited, 0);
	mem(lenth, 0x3f);
	visited[nowPos] = 1;
	lenth[nowPos] = 0;
	per(i,1,n) {
		per(j, 1, n+1) {
			if (mapp[nowPos][j] + lenth[nowPos] < lenth[j]) {
				lenth[j] = mapp[nowPos][j] + lenth[nowPos];
			}
		}
		int minPos = nowPos, minn = INF;
		per(j, 1, n+1) {
			if (!visited[j] && lenth[j] < minn) {
				minn = lenth[j];
				minPos = j;
			}
		}
		nowPos = minPos;
		visited[nowPos] = 1;
		if (nowPos == n) {
			break;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	while (cin >> n) {
		mem(mapp, 0x3f);
		cin >> m;
		per(i, 0, m) {
			cin >> u >> v >> w;
			if (mapp[u][v] > w) {
				mapp[u][v] = mapp[v][u] = w;
			}
		}
		dijkstra(1);
		if (lenth[n] == INF) {
			lenth[n] = -1;
		}
		cout  << lenth[n] << endl;
	}
	return 0;
}