初歩的なグラフの問題 (ID:72936)

名前

ホームページ(ブログ、Twitterなど)のURL (省略可)

本文

とりあえずコードを書いたほうがいいとのことでしたので、自分で考えた方法でコードを実装してみました。
まだコンパイルが通っただけで未テストです。
同じ地点を2度と通らないという条件で全2地点間を最短で結ぶコストを求めてみました。
まだプログラマとしては初心者レベルなのでコードがうまくいっているかどうかわからない状態です。

#include<stdio.h>

const int size=100;//グラフの最大サイズ、適当な値
const int max=1000000000;
const int memoSize=(size-1)/32+1;
int g[size][size];//グラフ
int rootMemo[size][size][memoSize];//グラフ間の2地点をつなぐ最大カロリー経路で通る地点を１bit単位で保存

bool connectOK(int k,int i,int j){
	//点iとk   kとｊを結ぶ最大カロリー経路に重複部分がないかチェック
	for(int l=0;l<memoSize;l++){
		if((rootMemo[i][k][l]&rootMemo[k][j][l])!=0) return false;
	}
	return true;
}

void connect(int k,int i,int j){
	for(int l=0;l<memoSize;l++){
		rootMemo[i][j][l]=rootMemo[i][k][l]|rootMemo[k][j][l];
	}
	rootMemo[i][j][k/32]|=(k%32);
}

void wf(int m){
	//拡張ワーシャルフロイド法
	int t;
	for(int k=0;k<m;k++){
		for(int i=0;i<m;i++){
			if(g[i][k]==max)continue;
			for(int j=0;j<m;j++){
				if(g[k][j]==max)continue;
				t=g[i][k]+g[k][j];
				if(t<g[i][j] && connectOK(k,i,j)){
					connect(k,i,j);
				}
			}
		}
	}
}
int main()
{
	int n,m;//nはノードの数、ｍは点の数,点は０からｍ−１まで番号をつける
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			g[i][j]=max;
			for(int k=0;k<memoSize;k++){
				rootMemo[i][j][k]=0;//経路の初期化
			}
		}
	}
	int a,b,c;
	for(int i=0;i<n;i++){
		scanf("%d %d %d",&a,&b,&c);//ノードの重み、道路で消費するカロリー。
		g[a][b]=g[b][a]=c;
	}
	for(int i=0;i<m;i++){
		scanf("%d",&c);//点で得られる重み、店舗で摂取できるカロリー
		for(int j=0;j<m;j++){
			if(g[j][i]!=max)g[j][i]-=c;
		}
		g[i][i]=max;
	}
	wf(m);
	//ここの時点で同じ地点を2度と通らず結んだ最短経路が配列ｇに出力されているはず
}

←解決時は質問者本人がここをチェックしてください。

戻る