POJ 3411 Paid Roads(DFSマルチアクセスノード)

題意:n都市はm道路で接続されており、2都市間に複数の道路がある可能性がある.これらの道路はすべて有料で、2つの有料方法があります.例えばaからb:方式1はbでrを支払う;方式2は、aの前に(aを含む可能性がある)有料pを支払うが、方式2有料要求経路はc点を通過しなければならない.1からnまでの最小費用を要求します.問題解:問題は最小費用のみを要求し,重いエッジが存在するため,複数のノードがアクセスされる可能性がある.したがって、各ノードのアクセス回数の上限を決定することが重要です.本題はいつも3を取ればいいようだ.

#include <vector>
#include <iostream>
using namespace std;

#define N 11
#define INF 99999

struct NODE
{
	int v, c, p, r;
} temp;

int vis[N], ans, n, m;
vector<NODE> node[N]; 

void dfs ( int u, int cost )
{
	vis[u]++;
	if ( cost >= ans ) return;

	if ( u == n )
	{
		if ( ans > cost ) 
			ans = cost;
		return;
	}

	int i, v, t;
	for ( i = 0; i < node[u].size(); i++ )
	{
		v = node[u][i].v;
		if ( vis[v] <= 3 ) //   ···
		{
			t = INF;
			if ( vis[node[u][i].c] && node[u][i].p < t ) 
				t = node[u][i].p;
			if ( node[u][i].r < t )
				t = node[u][i].r;
			dfs ( v, t + cost );
		    vis[v]--;
		}
	}
}


int main()
{
	int a, b, c, p, r;
	scanf("%d%d",&n,&m);
	memset(vis,0,sizeof(vis));

	while ( m-- )
	{
		scanf("%d%d%d%d%d",&a,&b,&c,&p,&r);
		temp.v = b;
		temp.c = c;
		temp.p = p;
		temp.r = r;
		node[a].push_back(temp);	
	}
	
	ans = INF;
	dfs ( 1, 0 );
	if ( ans != INF ) printf("%d
",ans);
	else printf("impossible
");
	
	return 0;
}