1382: 최 단 로 (Spfa)

[제목 설명]
정 하 다 MM 가닥 NN 개 점 의 대 권 무 향도.구하 다 11 까지 NN 의 최 단 로.
 
【 입력 】
첫 번 째 줄: N, M (N ≤ 100000, M ≤ 500000) N, M (N ≤ 100000, M ≤ 500000);
그 다음 에 MM 행 33 개의 정수: ai, bi, ci 는 ai, bi 사이 에 ci 의 길이 가 있 고 ci ≤ 1000 ai, bi, ci 는 ai, bi 사이 에 ci 의 길이 가 있 으 며 ci ≤ 1000 이다.
 
【 출력 】
하나의 정수 11 도착 하 다 NN 의 최 단 거리.
[샘플 입력]

4 4
1 2 1
2 3 1
3 4 1
2 4 1

[출력 사례]

2

[힌트]
[사례 설명]
그림 에 무 거 운 변 과 자체 고리, 데이터 보증 이 있 을 수 있 습 니 다. 11 도착 하 다 NN 경로 가 연결 되 어 있다.
 
 
그림 에 무 거 운 변 과 자체 고리, 데이터 보증 이 있 을 수 있 습 니 다. 11 도착 하 다 NN 경로 가 연결 되 어 있다.이 말 이 중요 해 요.
그래서 spfa 로.

#include
#include
#include
#include
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m;
struct node
{
	int next;
	int from, to, dis;
}s[3200000];
int head[320000];
int cnt;
void add_edge(int from, int to, int dis)
{
	s[++cnt].next = head[from];
	s[cnt].to = to;;
	s[cnt].dis = dis;
	head[from] = cnt;

}
int dis[250000];
int vis[250000];
void spfa()
{

	memset(dis, inf, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	vis[1] = 1;
	dis[1] = 0;
	queueQ;
	Q.push(1);
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		vis[u] = 0;
		for (int i = head[u];i;i = s[i].next) {
			int to = s[i].to;
			int di = s[i].dis;
			if (dis[to]>dis[u] + di) {
				dis[to] = dis[u] + di;
				if (!vis[to]) {
					vis[to] = 1;
					Q.push(to);
				}
			}
		}
	}

}
int main()
{
	scanf("%d %d", &n, &m);
	memset(head, 0, sizeof(head));
	for (int i = 0;i