さいたんらく

テーマURL:最短
この問題はfloydアルゴリズムを用いていたが,ここでは別のDijstraアルゴリズムを紹介する.
Dijstraアルゴリズムフロー:
(1)初期化,集合kはノード1に加え,ノード1から自分への最短経路は0,他のノードへはINFである.
(2)集合kノードに直接接続された辺(u,v,c)を遍歴し、ここでuは集合kに属し、vはkに属さず、ノード1から得られた最短路でuに到達し、さらにuからその辺を通ってvに到達する経路長を計算する.集合kにおけるノードに直接接続されていないすべての非集合kのノードの経路長を比較し、経路長が最も小さいノードは、次の最短経路で決定されたノードを決定し、その最短経路はこの経路長であり、最後にこのノードを集合kに加える.
(3)集合kにすべてのノードが含まれている場合,終了し,そうでなければ回転する(2).

#include
#include
#include
using namespace std;
struct e{//            
	int next;//         
	int cost;//       （  ）
};
const int INF = 123123123;
vector edge[101];//    
bool mark[101];//  ， mark[i] true    i           ，         k 
int dist[101];//  ， mark[i] true   ，dist[i]              ，         1  ，               k     ，
//          i        
int main()
{
	int n, m;
	while (cin >> n >> m&&n&&m)
	{
		for (int i = 1; i <= n; i++)
		{//   
			edge[i].clear();
			mark[i] = false;
			dist[i] = INF;//    dist[i]    -1，            
		}
		while (m--)
		{
			int a, b, c;
			cin >> a >> b >> c;
			e tmp;
			tmp.next = b;
			tmp.cost = c;
			edge[a].push_back(tmp);
			tmp.next = a;//      ，  
			edge[b].push_back(tmp);
		}
		dist[1] = 0;
		mark[1] = true;
		int newp = 1;
		for (int i = 1; i < n; i++)
		{
			for (int j = 0; j < edge[newp].size(); j++)
			{
				int t = edge[newp][j].next;
				int c = edge[newp][j].cost;
				if (mark[t])
					continue;//          k，      
				if (dist[t]>dist[newp] + c)//if(dist[t]==-1||dist[t]>dist[newp]+c)
				{//          ，                        
					dist[t] = dist[newp] + c;//       
				}
			}
			int min = 123123123;
			for (int j = 1; j <= n; j++)
			{//       ，    k ，            k  ，    mark true
				if (mark[j])
					continue;
				/*
				if(dist[j]==-1)
				   continue;
				*/
				if (dist[j] < min)
				{
					min = dist[j];
					newp = j;
				}
			}
			mark[newp] = true;
		}
		cout << dist[n] << endl;
	}
	return 0;
}
/**************************************************************
Problem: 1447
User: hellosyqq
Language: C++
Result: Accepted
Time:30 ms
Memory:1520 kb
****************************************************************/