제3 부분 데이터 구조 제4 장 도 론 알고리즘 제2 절 최 단 경로 알고리즘 1382: 최 단 경로 (Spfa)

1382: 최 단 로 (Spfa)
시간 제한: 1000 ms 메모리 제한: 65536 KB 제출 수: 2196 통과 수: 592 [제목 설명] 주어진 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, 3, 4, 1, 2, 1 [출력 샘플] 2 [힌트] [샘플 설명]
그림 에 무 거 운 변 과 자체 고리 가 있 을 수 있 습 니 다. 데 이 터 는 11 에서 NN 까지 경로 가 연결 되 어 있 습 니 다.

#include
#include
#include
#include
const int NN=100001;
using namespace std;
struct node
{
	int from,go,money;
};
vector<int>g[NN];
vector<node>N;
bool inq[NN];
int d[NN];
queue<int>a;
int n,m;
void e(int from,int go,int money)
{
	N.push_back((node){from,go,money});
	g[from].push_back(N.size()-1);
}
int main()
{
	scanf("%d %d",&n,&m);
	fill_n(d,100002,999999);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		e(x,y,z);
		e(y,x,z);
	}
	d[1]=0;
	a.push(1);
	inq[1]=true;
	while(!a.empty())
	{
		int u=a.front();
		a.pop();
		inq[u]=false;
		for(int i=0;i<g[u].size();i++)
		{
			node e=N[g[u][i]];
			if(e.money+d[u]<d[e.go])
			{
				d[e.go]=e.money+d[u];
				if(!inq[e.go])
				{
					a.push(e.go);
					inq[e.go]=true;
				}
			}
		}
	}
	printf("%d",d[n]);
	return 0;
}