ディジェストラ最短パスアルゴリズム

問題A:アルゴリズム7-15:ディジェストラ最短パスアルゴリズム

時間制限:1 Sec
メモリ制限:32 MB

タイトルの説明

重み付き有向図Gでは、1つのソース点vが与えられ、vからGまでの残りの各頂点の最短経路問題を、単一ソース点の最短経路問題と呼ぶ.
一般的な単一ソース点最短経路アルゴリズムでは、ディジェストラアルゴリズムが最も一般的であり、経路長が増加する順序で最短経路を生成するアルゴリズムである.
ディジェストラアルゴリズムは次のように記述できます.
本題では、有向図の重み付き隣接行列(すなわち配列表現)を読み込み、有向図を確立し、以上の説明のアルゴリズムに従ってソース点から他の頂点までの最短経路長を求める.

入力

入力された最初の行は2つの正の整数nとsを含み、図にはn個の頂点があり、ソース点はsであることを示す.ここで、nは50を超えず、sはnより小さい.
以降のn行の各行には、スペースで区切られたn個の整数がある.i行目のj番目の整数について、0より大きい場合、i番目の頂点はj番目の頂点を指す有向辺があり、重み値は対応する整数値であることを示す.この整数が0である場合、iがjを指す有向辺がないことを示す.iとjが等しい場合、対応する整数が0であることを保証する.

しゅつりょく

1行のみで、n-1個の整数があり、ソースポイントから他の各頂点への最短パス長を表します.ソースポイントから対応する頂点へのパスが存在しない場合は、-1を出力します.
行末出力改行に注意してください.

サンプル入力

4 1

0 3 0 1

0 0 4 0

2 0 0 0

0 0 1 0

サンプル出力

6 4 7 

ヒント

本題では,タイトル記述のアルゴリズムに従ってディジェストラアルゴリズムを完成させ,最短経路を計算する過程で各頂点が達できるかどうかを記録し,各達頂点の最短経路が求められるまでアルゴリズムを終了させる必要がある.
ディジェストラアルゴリズムの特徴は、パスの長さが増加する順序で、次の長さが最も短いエッジを順次追加し、対応する頂点の最短パスを絶えず構築することです.
なお,本題では,頂点間の到達不能状態をより容易に表すために,非常に大きな値をタグとして用いることができる.

#include
#include
#include
#define inf 0x3f3f3f3f
#define maxn 55
using namespace std;
struct list
{
	int des;
	int weight;
	list() {	}
	list(int a,int b)
	{
		des=a;
		weight=b;
	}
	friend bool operator d.weight;
	}
};
struct Edge
{
	int v;
	int w;
	int next;
}edge[maxn*maxn];
int head[maxn],cnt,dis[maxn];
bool vis[maxn];
void add_edge(int u,int v,int w)
{
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
void dijkstra(int s)
{
	priority_queue q;
	memset(dis,inf,sizeof(dis));
	dis[s]=0;
	q.push(list(s,dis[s]));
	while(!q.empty())
	{
		struct list Q=q.top();
		q.pop();
		if(vis[Q.des])
			continue;
		vis[Q.des]=true;
		for(int i=head[Q.des];i!=-1;i=edge[i].next)
		{
			int to=edge[i].v;
			if(dis[to]>dis[Q.des]+edge[i].w)
			{
				dis[to]=dis[Q.des]+edge[i].w;
				q.push(list(to,dis[to]));
			}
		}
	}
}
int main()
{
	int n,s,d;
	cnt=0;
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&s);
	for(int i=0;i