【C++】最短パステンプレート問題回答

70604 ワード

【推薦コラム】一連の問題解同前 C++ コード

文書ディレクトリ

Floydアルゴリズム

題

ヒント

コード

Dijkstraアルゴリズム

題

ヒント

コード

Spfaアルゴリズム

題

ヒント

コード1

コード2

Floydアルゴリズム
タイトル
HihoCoder-1089 vjudge
ヒント
Hoさんは「君の言うことは筋が通っている.私はノードごとにDijstraアルゴリズムを使うだけだ」と話した.
Hiさんは「問題を解決することは肝心ではなく、知識を学ぶことが肝心で、知識自体も勉強の方法をはるかに把握していない」と首を横に振った.
Hoさんは「はい、はい、あなたの言うことを聞いてください」と答えなければなりません.
するとHiさんは、「今回お話しするアルゴリズムをFloydアルゴリズムといい、図の構造上の任意の2点間の最短距離を求めるアルゴリズムです!」と喜んだ.
Hoさんは「タイトルに書いてあるのに、知らないわけにはいかないだろう」とつぶやいた.
Hiちゃんは「このアルゴリズムの核心は数学的帰納法であるMinDistance(i,j)間の最短経路で使えるノードが少しずつ増えていることにある」と強引に耳を貸さないふりをして続けた.
「あなたのこの話はどの字も分かりますが、この言葉はどうして分からないのですか......」Hoさんは仕方がありません.
「それでは、まず最初、MinDistance(i,j)--つまりi番目の点からj番目の点までの最短経路の長さには、この経路がノードを通過できないという制限があります.」小Hi道.
「つまり、i個目からj個目までの間に直接つながっている辺がなければ、この長さは無限大になるということですか?」Hoさんは「入力したエッジをMinDistanceに記入するだけでいい」とまとめた.
「そうだ!」HiちゃんはHoちゃんの上道に満足して、続けて言いました.「それから制限を外して、MinDistance(i,j)--i番目の点からj番目の点までの最短経路の長さを許可して、制限を持って、この経路は1番のノードしか通過できないようになりました.」
「これも簡単で、2つのノードi,jについては、MinDistance(i,j)の元の値とMinDistance(i,1)+MinDistance(1,j)の値を比較し、小さいものを新しいMinDistance(i,j)として取得すればよい.元のMinDistanceはいずれのノードも通過しないので、このようにして求められた新しいMinDistance(i,j)は1番のノードしか通過できない」
「それでは、次が肝心です.私は制限を緩和し続けます.パスは1、2番ノードしか通過できません.」Hiちゃんは言い続けた.
「それは何の変化もないでしょう.2つのノードi,jについて、私はMinDistance(i,j)の元の値とMinDistance(i,2)+MinDistance(2,j)の値を比較して、新しいMinDistance(i,j)として小さい値を取る必要があります.だから新しく求めたMinDistance(i,j)も1,2番ノードしか通れない!“
「じゃあ、私は制限を外し続けますか?」Hiちゃんが尋ねた.
「別に違いはありません.私たちが要求したい値です.偽のコードを書くのはそうです.」

for k = 1 .. N
    for i = 1 .. N 
        for j = 1 .. N
             i, j, k    
                MinDistance[i, j] = min{MinDistance[i, j], MinDistance[i, k] + MinDistance[k, j]}

「よくわかったね」Hiちゃんはへへへへと笑って、お化け屋敷の奥へ走っていきました.では、次はHoちゃんが求めた最短ルートを利用して、Hiちゃんを見つけに行く時です.
コード#コード#

#pragma GCC optimize(3,"Ofast","inline")
#pragma G++ optimize(3,"Ofast","inline")

#include 
#include 
#include 
#include 
#include 

#define RI                 register int
#define re(i,a,b)          for(RI i=a; i<=b; i++)
#define ms(i,a)            memset(a,i,sizeof(a))
#define MAX(a,b)           (((a)>(b)) ? (a):(b))
#define MIN(a,b)           (((a)

using namespace std;

typedef long long LL;

const int N=1005;
const int inf=0x3f3f3f;

int n,m;
int f[N][N];

int main() {
	scanf("%d%d",&n,&m);
	memset(f,inf,sizeof(f));
	for(int i=1; i<=m; i++) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		f[u][v]=MIN(f[u][v],w);
		f[v][u]=MIN(f[v][u],w);
	}
	for(int k=1; k<=n; k++) 
		for(int i=1; i<=n; i++) 
			for(int j=1; j<=n; j++) 
				f[i][j]=MIN(f[i][j],f[i][k]+f[k][j]);
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) 
			printf("%d ",(i==j) ? 0 : f[i][j]);
		printf("
");
	}
	return 0;
}

Dijkstraアルゴリズム
タイトル
HihoCoder-1089 vjudge
ヒント
Hoさんは考えて言いました.「うーん、ダイナミックプランニングはできると思いますが、計算の順番が見つかりません.Sからiという番号のノードまでの最短距離をf[i]で表すと、f[1]...f[N]の計算の順番がわかりません.」
「だからこの問題はそんなに複雑なアルゴリズムはいらない.ちょっと話してみればわかるよ」小Hiは「道の長さがマイナスになるわけがないでしょう」と言った.
「それは自然です.人間はまだタイムマシンを発明していませんから......」Hoさんはうなずいた.
するとHiさんは、「Sに隣接するすべてのノードの中でSに最も近いS’を見て、SからS’までの距離がLであれば、SからS’までの距離がLより小さいような別の道がある可能性があるのか」と尋ねた.
「いいえ、S’はSに隣接するすべてのノードの中でSに最も近いノードであるため、Sから他の隣接点までの距離はLより小さくないに違いありません.つまり、次にどのように歩いても、L点に戻るときの総距離はLより大きいに違いありません.」Hoさんはしばらく考えていました.
「つまり、SからSへの最短経路を知っていますよね?」Hiちゃんは尋ね続けた.
「はい、この最短経路の長さはLです」Hoちゃんは答えた.
Hiちゃんは続けた.「それでは、SとS’を新しいノードと見なしてみてはいかがでしょうか.S 1と呼びます.そして、Sに隣接するノードまたはS’に隣接するすべてのノードのうち、Sに最も近いノードS’’を計算します.この過程で、Sに隣接するノードとSとの距離が前のステップで求められたので、S’に隣接するノードとSとの距離だけが求められます-この距離はSとS’の距離にS’とこれらのノードとの距離を加え、重複するノードであるSとS’に隣接するノードについて、2つのパスのうちの小さい値をとる.」
Hoちゃんはうなずいた.
そこでHiさんは、「次の問題は簡単ではないか.選択して現在のコレクションに追加すると、各ノードがコレクションに追加されたときに計算されるSからの距離がSとの最短パスであることを保証できます.」
「そうだったのか!でももっとお腹が減ったんだよ!」と言って、ホッちゃんのお腹がグーグーと鳴いた.
コード#コード#
Dijkstra:

#pragma GCC optimize(3,"Ofast","inline")
#pragma G++ optimize(3,"Ofast","inline")

#include 
#include 
#include 
#include 
#include 

#define RI                 register int
#define re(i,a,b)          for(RI i=a; i<=b; i++)
#define ms(i,a)            memset(a,i,sizeof(a))
#define MAX(a,b)           (((a)>(b)) ? (a):(b))
#define MIN(a,b)           (((a)

using namespace std;

typedef long long LL;

const int N=1005;
const int inf=0x3f3f3f;

int n,m,s,t;
int d[N],vis[N];
int a[N][N];

void dijkstra() {
	memset(vis,0,sizeof(vis));
	for(int i=1; i<=n; i++) d[i]=inf;
	d[s]=0;
	for(int i=1; i<=n; i++) {
		int k=-1;
		for(int j=1; j<=n; j++)
			if(!vis[j] && (k==-1 || d[k]>d[j])) k=j;
		vis[k]=1;
		for(int j=1; j<=n; j++)
			if(!vis[j] && d[k]+a[k][j]<d[j])
				d[j]=d[k]+a[k][j];
	}
}

int main() {
	scanf("%d%d%d%d",&n,&m,&s,&t);
	memset(a,inf,sizeof(a));
	for(int i=1; i<=m; i++) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		a[u][v]=MIN(a[u][v],w);
		a[v][u]=MIN(a[v][u],w);
	}
	dijkstra();
	printf("%d
",d[t]==inf ? -1 : d[t]);
	return 0;
}

スタック最適化Dijkstra:

#pragma GCC optimize(3,"Ofast","inline")
#pragma G++ optimize(3,"Ofast","inline")

#include 
#include 
#include 
#include 
#include 
#include 

#define RI                 register int
#define re(i,a,b)          for(RI i=a; i<=b; i++)
#define ms(i,a)            memset(a,i,sizeof(a))
#define MAX(a,b)           (((a)>(b)) ? (a):(b))
#define MIN(a,b)           (((a)

using namespace std;

typedef long long LL;

const int N=1005;
const int M=10005;
const int inf=0x3f3f3f;

struct Edge {
	int to,nt,w;
} e[M<<1];

struct Node {
	int index,dist;
	
	bool operator < (const Node &rhs) const {
		return dist>rhs.dist;
	}
};

int n,m,s,t,cnt;
int d[N],vis[N],h[N];

priority_queue<Node> q;

inline void add(int u,int v,int w) {
	e[++cnt].to=v;
	e[cnt].nt=h[u];
	e[cnt].w=w;
	h[u]=cnt;
}

void dijkstra() {
	memset(vis,0,sizeof(vis));
	for(int i=1; i<=n; i++) d[i]=inf;
	d[s]=0;
	q.push((Node){s,0});
	while(!q.empty()) {
		Node x=q.top();
		q.pop();
		int u=x.index;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=h[u]; i; i=e[i].nt) {
			int v=e[i].to;
			if(d[v]>d[u]+e[i].w) {
				d[v]=d[u]+e[i].w;
				q.push((Node){v,d[v]});
			}
		}
	}
}

int main() {
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1; i<=m; i++) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dijkstra();
	printf("%d
",d[t]==inf ? -1 : d[t]);
	return 0;
}

Spfaアルゴリズム
タイトル
HihoCoder-1089
vjudge
ヒント
「うーん、場所が多くて、道が少ない.このお化け屋敷はまばらな図だ.それがわざわざ表記されている以上、役に立つと思う?」小Ho道.
「はい、ちょうど最短パスアルゴリズムがあります.時間の複雑さはエッジのストライプ数に関係しているだけなので、このエッジの数が少ない最短の問題を解決するのに特に適しています.」Hiちゃんは「SPFAアルゴリズム、すなわちShortest Path Faster Algorithmです」とうなずいた.
「すごいように聞こえますが、実際にはどうやって作ったんですか?」Hoさんが尋ねた.
「幅優先検索でこの問題を書きますか?」Hiちゃんは聞き返した.
「もちろんですよ.最初のキューには(S,0)しかありません.--iとjの間に長さlの辺があることを示し、(j,L+l)を隊尾に加え、最後に遍歴した(T,X)ノードのXの最小値がすべて答えだよ~」とHoさんは検索に慣れていて、口を開けた.
「SPFAアルゴリズムは、ある意味では幅優先探索の最適化である.このノードは実際に検索を続ける必要はありません.最適化された枝ですね.q<q’であれば(p,q’)検索を続ける必要はありませんが、キューに存在したらどうしますか?簡単です.キューの(p,q’)を(p,q)に変更すればいいです.」
「じゃあ、キューに(p,q’)があるかどうか、どうやって知るの?」「だから本質的には幅優先検索の枝なの?」Hoさんが尋ねた.
Hiちゃんは「まさか!SPFAアルゴリズムはBELLMAN-FORDアルゴリズムの最適化バージョンなんですが、成形後は幅優先検索として理解できるようになりました!この問題は、後で詳しくお話しします!」と笑顔を見せた.
コード1
vectorで実現します.

#pragma GCC optimize(3,"Ofast","inline")
#pragma G++ optimize(3,"Ofast","inline")

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define RI                 register int
#define re(i,a,b)          for(RI i=a; i<=b; i++)
#define ms(i,a)            memset(a,i,sizeof(a))
#define MAX(a,b)           (((a)>(b)) ? (a):(b))
#define MIN(a,b)           (((a)

using namespace std;

typedef long long LL;

const int N=1e5+5;
const int inf=1e9;

int n,m,s,t;
int v[N],d[N];

vector<int> a[N],b[N];
queue<int> q;

int spfa() {
	for(int i=1; i<=n; i++) d[i]=inf;
	q.push(s);
	v[s]=1;
	d[s]=0;
	while(!q.empty()) {
		int x=q.front();
		q.pop();
		v[x]=0;
		for(int i=0; i<a[x].size(); i++) {
			int tp=a[x][i];
			if(d[tp]>d[x]+b[x][i]) {
				d[tp]=d[x]+b[x][i];
				if(!v[tp]) {
					q.push(tp);
					v[tp]=1;
				}
			}
		}
	}
	if(d[t]==inf) d[t]=-1;
	return d[t];
}

int main() {
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1; i<=m; i++) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		a[u].push_back(v);
		b[u].push_back(w);
		a[v].push_back(u);
		b[v].push_back(w);
	}
	printf("%d
",spfa());
	return 0;
}

コード2
チェーン式前方星で実現.

#pragma GCC optimize(3,"Ofast","inline")
#pragma G++ optimize(3,"Ofast","inline")

#include 
#include 
#include 
#include 
#include 
#include 

#define RI                 register int
#define re(i,a,b)          for(RI i=a; i<=b; i++)
#define ms(i,a)            memset(a,i,sizeof(a))
#define MAX(a,b)           (((a)>(b)) ? (a):(b))
#define MIN(a,b)           (((a)

using namespace std;

typedef long long LL;

const int N=1e5+5;
const int M=1e6+5;
const int inf=1e9;

struct Edge {
	int to,nt,w;
} e[M<<1];

int n,m,s,t,cnt;
int v[N],d[N],h[N];

queue<int> q;

inline void add(int a,int b,int c) {
	e[++cnt]=(Edge){b,h[a],c};
	h[a]=cnt;
}

int spfa() {
	for(int i=1; i<=n; i++) d[i]=inf;
	q.push(s);
	v[s]=1;
	d[s]=0;
	while(!q.empty()) {
		int x=q.front();
		q.pop();
		v[x]=0;
		for(int i=h[x]; i; i=e[i].nt) {
			int tp=e[i].to;
			if(d[tp]>d[x]+e[i].w) {
				d[tp]=d[x]+e[i].w;
				if(!v[tp]) {
					q.push(tp);
					v[tp]=1;
				}
			}
		}
	}
	if(d[t]==inf) d[t]=-1;
	return d[t];
}

int main() {
	scanf("%d%d%d%d",&n,&m,&s,&t);
	memset(h,-1,sizeof(h)); 
	for(int i=1; i<=m; i++) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	printf("%d
",spfa());
	return 0;
}

Cプログラムオブジェクト向け設計の詳細

rails save! create! update!のバリデーション例外を捕捉する