「CQOI 2005」新年おめでとう-最短経路

19444 ワード

タイトルの説明
重慶城にはnつの駅があり、m本の双方向道路がその中のいくつかの駅を接続している.2つの駅ごとに最大1つの道路で接続され、どの駅からも1つ以上の道路を通って他の駅に着くことができるが、経路によって時間がかかる可能性がある.1つの経路にかかる時間は、経路上のすべての道路に必要な時間の和に等しい.佳佳の家は駅の1にあって、彼は5人の親戚がいて、それぞれ駅のa,b,c,d,e.に住んでいて、彼は自分の家から出発して、すべての親戚を訪問して(順番は任意です)、彼らに祝日の祝福を送ります.どうやって行けば、一番少ない時間がかかりますか?
入力フォーマット
1行目:n,mは駅数と道路数である.2行目:a,b,c,d,eは、5人の親戚がいる駅番号です.以下のm行は、行ごとに3つの整数x,y,tであり、道路が接続する2つの駅番号と時間である.
出力フォーマット
1行のみ、1つの整数Tを含む、最小の総時間である.
サンプル入力
6 6 2 3 4 5 6 1 2 8 2 3 3 3 4 4 4 5 5 5 6 2 1 6 7
サンプル出力
21
データ規模と約定
1 ≤ n ≤ 500000 , 1 ≤ m ≤ 1000000 ; 1\le n\le 500000,1\le m\le 1000000; 1≤n≤500000,1≤m≤1000000; 1 < a , b , c , d , e ≤ n ; 1ぶんせき
重慶省の選題として、この問題は比較的水のようだ.a,b,c,d,e,1 a,b,c,d,e,1 a,b,b,c,c,d,1 a,b,c,d,e,1番ノードと他のノードとの最短回路を先にspfaで飛び出し、さらに暴力的に訪問順序を列挙し、最短の経路長を求めることができる.
コード#コード#

#include 
#include 
#include 
#include 
#define inf 0x7fffffff/2
using namespace std;
struct node {
	int to,next,wei;
}e[200005];
int h[50005],cnt,a[10];
int dt[50];
int d[7][50005],vis[50005];
int n,m,ans=inf;
void adg(int x,int y,int z) {
	e[++cnt]=(node){y,h[x],z};
	h[x]=cnt;
}
void spfa(int v0,int k) {
	queue<int> q;
	int book[50005]={0};
	q.push(v0);
	book[v0]=1;
	d[k][v0]=0;
	while (!q.empty()) {
		int w=q.front();
		q.pop();
		book[w]=0;
		for (int i = h[w];i;i=e[i].next) {
			int y=e[i].to;
			if (d[k][y]>d[k][w]+e[i].wei) {
				d[k][y]=d[k][w]+e[i].wei;
				if (!book[y]) {
					book[y]=1;
					q.push(y);
				}
			}
		}
	}
}
void dfs(int k) {
	if (k==6) {
		int s=0;
		for (int i = 1;i < 6;i++) {
			s+=d[dt[i]][a[dt[i+1]]];
		}
		ans=min(ans,s);
		return;
	}
	for (int i = 2;i <= 6;i++) {
		if (!vis[i]) {
			vis[i]=1;
			dt[k+1]=i;
			dfs(k+1);
			vis[i]=0;
		}
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for (int i = 2;i <= 6;i++) {
		scanf("%d",a+i);
	}
	for (int i = 1;i <= m;i++) {
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		adg(a,b,c);
		adg(b,a,c);
	}
	memset(d,127,sizeof(d));
	a[1]=1;
	dt[1]=1;
	for (int i = 1;i <= 6;i++) {
		spfa(a[i],i);
	}
	dfs(1);
	printf("%d",ans);
	return 0;
}

CakePHP3系の個人用メモ

cakephp2のインストールはcomposer.jsonにphpのバージョンを明記