problem: POJ3255

#include<bits/stdc++.h>

using namespace std;

int n, m;

priority_queue<pair<int, int>> q;

int tot;

int root;

const int NR = 5e4 + 1, MR = 1e5 + 1; 

int head[NR], nxt[2 * MR], to[2 * MR], edge[2 * MR];

int d[NR];

int dis[NR];

int v[NR];

void add(int x, int y, int z)
{
	to[++tot] = y;
	edge[tot] = z;
	nxt[tot] = head[x];
	head[x] = tot;
}

void dij()
{
	memset(d, 0x3f, sizeof d);
	memset(dis, 0x3f, sizeof dis);
	v[root] = 1;
	d[root] = 0;
	q.push(make_pair(0, root));
	while(!q.empty()){
		int x = q.top().second, xx = -q.top().first; q.pop();
		if(dis[x] < xx) continue;
		if(v[x] == 2) continue;
		v[x]++;
		for(int i=head[x]; i; i = nxt[i])
		{
			int y = to[i], z = edge[i];
			int t = d[x] + z;
			if(d[y] > t)
			{
				swap(d[y], t);
				q.push(make_pair(-d[y], y));
			}
			if(t > d[i] && t < dis[y])
			{
				dis[y] = t;
				q.push(make_pair(-dis[y], y));
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
	}
	root = 1;
	dij();
	if(dis[n] == 0x3f3f3f3f) cout << -1;
	else cout << dis[n];
    return 0;
}

sample:

4 4
1 2 100
2 4 200
2 3 250
3 4 100

450