HDUOJ 1874プロジェクト継続とNYOJ 115都市平乱【Dijkstraアルゴリズム】

本題リンク:nyoj 115:http://acm.nyist.net/JudgeOnline/problem.php?pid=115      hduoj 1874: http://acm.hdu.edu.cn/showproblem.php?pid=1874
  一、Dijkstraアルゴリズムの紹介
    Dijkstraアルゴリズムは、ディコス徹アルゴリズムとも呼ばれます.    アルゴリズムで解決したのは,図中の単一ソース点から他の頂点への最短経路問題である.   例えば、   図の頂点が都市を表している場合、その辺の重みは都市間の運転距離を表しています.   Dijkstraアルゴリズムは2つの都市間の最短経路を見つけるために使用できます.
二、Dijkstraのアルゴリズム実現
Dijkstraアルゴリズムの入力は、図GとGのソース頂点Sとの間の重みがある.G中のすべての頂点の集合をVで表し、G中のすべての辺の集合をEで表します.(u,v)は頂点uからvまでの経路が接続されていることを示し、辺の重みは重み関数w:E→[0、∞]によって定義される.
このため、w(u,v)は頂点uから頂点vまでの非負のコスト(cost)であり、辺のコストは2つの頂点間の距離と考えられます.2点間のパスの費用の値は、このパスのすべての辺の合計です.
Vには頂点sおよびtがあることが知られていますが、Dijkstraアルゴリズムはsからtまでの最低のコスト経路(例えば、最短の経路)を見つけることができます.このアルゴリズムはまた、一つの図において、一つの頂点sから他の頂点までの最短経路を見つけることができる.
三、図面解析 Dijkstraアルゴリズム
 前の文を通して、ちょっと複雑な情報がありますが、まだこのアルゴリズムについてはよく分かりません.大丈夫です.絵を描いてきます.このアルゴリズムの概念を述べさせていただきます.
Dijkstraアルゴリズムは、他のすべてのノードへのノードの最短経路を計算するための典型的な最短経路アルゴリズムである.ただし、対象は非マイナス側です.
スタートポイントを中心に外側に層を広げ、ゴールまで広げていくのが主な特徴です.[Dijkstraアルゴリズムは最短経路の最適解を得ることができますが、計算ノードが多いので、効率が低いです.]
ok、下の図を見てください.
下の図のように、Aをソースとして、他の各1つの頂点(B、C、D、E、F)までの最短経路を求めます.線に隣接する線分間の距離として表示されています.
(注:この図は任意に描かれています.隣の頂点間の距離は図中の目視長とは一対一ではないです.)
               Dijkstraには方向図がありません

アルゴリズム実行ステップは以下の表の通りです.

 Dijkstraアルゴリズムについてよく知っていますか?説明はここまでです.
説明の参考:http://blog.csdn.net/v_JULYv/articale/detail/6096981
今はojという二つの問題について話します.
ニャンコ 115:dijkstraが分かりました.問題は難しくないです.暴動都市を起点に一回実行します. 彼が各都市の最短距離に行くことを求めて、更に部隊がある都市を探して、1つの最も小さい道の出力を探し当てます.
コード:

 
#include<stdio.h>
#include<string.h>
int budui[105],ok[1005][1005];
int ac[1005],yi[1005];
int main()
{
	int a,b,c,i,j,N,M;
	int m,P,Q,K,k,min;
	scanf("%d",&K);
	while(K--)
	{
		memset(ok,999999,sizeof(ok));//       
		memset(ac,0,sizeof(ac));
		memset(yi,999999,sizeof(yi));
		scanf("%d%d%d%d",&N,&M,&P,&Q);
			for(a=1;a<=N;a++)
			scanf("%d",&budui[a]);
	    for(a=1;a<=P;a++)
		{
			scanf("%d%d%d",&i,&j,&k);
            ok[i][j]=k;
			ok[j][i]=k;
		}
		yi[Q]=0;
		ac[Q]=1;
		m=M-1;
		b=Q;
		while(m--)//  m ，                
		{
			for(a=1;a<=M;a++)
			{
				if(ac[a]==0)
				{
					if(yi[a]>yi[b]+ok[a][b])
						yi[a]=yi[b]+ok[a][b];
				}
				
			}
			int min1=9999,loop;
			for(c=1;c<=M;c++)
			{
				if(min1>yi[c]&&ac[c]==0)
				{min1=yi[c];loop=c;}
			}
			ac[loop]=1;
			b=loop;
		}
		 min=9999;
		for(a=1;a<=N;a++)//              
		{
			if(min>yi[budui[a]])
				min=yi[budui[a]];
		}
		printf("%d
",min);
	}
}
        

     HUOJ 1874:
    この問題はちょっとあれですか?長い間カードを使いました.やはり題意が徹底していない.唳唵.まず使って、集を調べて、問題中のS Tを判断して、つながってもいいですか?もう一つの記事を見て、ブログを調べます.自分で探してみます.もし接続しないなら、後は実行しなくてもいいです.直接に次の循環をします.卵が痛いという条件は二つの都市の間に一つの道がないかもしれません.は、賦課時にi f判定を加えることです.
コード:

#include<stdio.h>
#include<string.h>
int ok[1500][1500];
int ac[1505],yi[1500];
int father[1500];
int find(int x)
{
	while(x!=father[x])
		x=father[x];
	return x;
}
void hebing (int x,int y)
{
	x=find(x);
	y=find(y);
	if(x!=y)
		father[x]=y;
}
int main()
{
	int a,b,c,i,j,N,M;
	int m,k,min;
	while(~scanf("%d%d",&N,&M))
	{
		
		memset(ok,9,sizeof(ok));
		memset(ac,0,sizeof(ac));
		memset(yi,9,sizeof(yi));
		for(a=0;a<N;a++)
			father[a]=a;
	    for(a=1;a<=M;a++)
		{
			scanf("%d%d%d",&i,&j,&k);
			if(ok[i][j]>k)
                 ok[i][j]=k;
			if(ok[j][i]>k)
			     ok[j][i]=k;
			hebing(i,j);
		}
		scanf("%d%d",&i,&j);
		if(find(i)!=find(j))
		{printf("-1
");continue;}
		yi[i]=0;
		ac[i]=1;
		m=N-1;
		b=i;
		while(m--)
		{
			for(a=0;a<N;a++)
			{
				if(ac[a]==0)
				{
					if(yi[a]>yi[b]+ok[a][b])
						yi[a]=yi[b]+ok[a][b];
				}
				
			}
			int min1=9999999,loop;
			for(c=0;c<N;c++)
			{
				if(min1>yi[c]&&ac[c]==0)
				{min1=yi[c];loop=c;}
			}
			ac[loop]=1;
			b=loop;
			if(b==j)
			{break;}
		}
		 printf("%d
",yi[j]);
	}
}