noip2012 文化之旅 （深搜，最優性剪枝）

P2070 [NOIP2012P4]文化之旅

時間: 1000ms / 空間: 131072KiB / Java類名: Main

背景

NOIP 2012 普及組 題4

描述

有一位使者要遊曆各國，他每到一個國家，都能學到一種文化，但他不願意學習任何一種文化超過一次（即如果他學習了某種文化，則他就不能到達其他有這種文化的國家）。不同的國家可能有相同的文化。不同文化的國家對其他文化的看法不同，有些文化會排斥外來 文化（即如果他學習了某種文化，則他不能到達排斥這種文化的其他國家）。

       現給定各個國家間的地理關系，各個國家的文化，每種文化對其他文化的看法，以及這 位使者遊曆的起點和終點（在起點和終點也會學習當地的文化），國家間的道路距離，試求 從起點到終點最少需走多少路。 

輸入格式

第一行為五個整數 N，K，M，S，T，每兩個整數之間用一個空格隔開，依次代表國家 個數（國家編号為 1 到 N），文化種數（文化編号為 1 到 K），道路的條數，以及起點和終點 的編号（保證 S 不等于 T）；

       第二行為 N 個整數，每兩個整數之間用一個空格隔開，其中第 i 個數 Ci，表示國家 i 的文化為 Ci。

       接下來的 K 行，每行 K 個整數，每兩個整數之間用一個空格隔開，記第 i 行的第 j 個數 為 aij，aij= 1 表示文化 i 排斥外來文化 j（i 等于 j 時表示排斥相同文化的外來人），aij= 0 表示 不排斥（注意 i 排斥 j 并不保證 j 一定也排斥 i）。

       接下來的 M 行，每行三個整數 u，v，d，每兩個整數之間用一個空格隔開，表示國家 u

       與國家 v 有一條距離為 d 的可雙向通行的道路（保證 u 不等于 v，兩個國家之間可能有多條 道路）。

輸出格式

       輸出隻有一行，一個整數，表示使者從起點國家到達終點國家最少需要走的距離數（如果無解則輸出-1）。

測試樣例1

輸入

樣例1：

2 2 1 1 2

1 2

0 1

1 0

1 2 10

樣例2：

2 2 1 1 2

1 2

0 1

0 0

1 2 10

輸出

樣例1：

-1

樣例2：

10

備注

對于樣例1：

由于到國家2必須要經過國家1，而國家2的文明卻排斥國家1的文明，是以不可能到國家2。

對于樣例2：

路線為1->2。

【資料範圍】

對于 20%的資料，有 2≤N≤8，K≤5；

對于 30%的資料，有 2≤N≤10，K≤5；

對于 50%的資料，有 2≤N≤20，K≤8；

對于 70%的資料，有 2≤N≤100，K≤10；

對于 100%的資料，有 2≤N≤100，1≤K≤100，1≤M≤N2，1≤ki≤K，1≤u, v≤N，1≤d≤1000， S≠T，1 ≤S, T≤N。

解析：最優性剪枝。用floyd計算出任意兩點間的可能最短距離（不考慮同色或者排斥），假設搜尋到點 i ，已走len，若len+map[i][t]>=ans,那麼就沒有繼續搜尋的必要了。

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100
using namespace std;

int ans,n,p,m,s,t;
int c[maxn+10],map[maxn+10][maxn+10],q[maxn+10];
bool b[maxn+10][maxn+10],flag[maxn+10];

void readdata()
{
  int i,j,k,u,v,d;
  scanf("%d%d%d%d%d",&n,&p,&m,&s,&t);
  for(i=1;i<=n;i++)scanf("%d",&c[i]);
  
  for(i=1;i<=p;i++)
    for(j=1;j<=p;j++)
      scanf("%d",&k),b[i][j]=k;
  for(i=1;i<=p;i++)b[i][i]=1;
  
  if(b[c[t]][c[s]]){printf("-1\n");exit(0);}
  
  memset(map,90,sizeof(map));    
  for(i=1;i<=m;i++)
    {
      scanf("%d%d%d",&u,&v,&d);
      map[u][v]=map[v][u]=d;
    }
  for(i=1;i<=n;i++)map[i][i]=0;   
}

void dfs(int x,int len)
{
  if(x==t){ans=min(ans,len);return;}
  
  int i,j,k,l,r;
  for(i=1;i<=n;i++)
    if(!flag[i] && ans-len-map[x][i]>map[i][t])
      {
        l=q[0]+1;
        q[++q[0]]=i,flag[i]=1;
        for(j=1;j<=n;j++)
      if(!flag[j] && b[c[j]][c[i]])
        q[++q[0]]=j,flag[j]=1;
    r=q[0];
    dfs(i,len+map[x][i]);
    for(j=l;j<=r;j++)flag[q[j]]=0;
    q[0]=l-1;    
      }
}

void work()
{
  int i,j,k;
  for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)if(!b[c[k]][c[i]])
      for(j=1;j<=n;j++)if(!b[c[j]][c[k]] && !b[c[j]][c[i]])
        if(map[i][j]-map[i][k]>map[k][j])map[i][j]=map[i][k]+map[k][j];

  for(i=1;i<=n;i++)if(i!=s && i!=t)
    if(b[c[i]][c[s]] || b[c[t]][c[i]])q[++q[0]]=i,flag[i]=1;
  
  ans=map[maxn+5][maxn+5];
  q[++q[0]]=s,flag[s]=1,dfs(s,0);  
  if(ans==map[maxn+5][maxn+5])printf("-1\n");
  else printf("%d\n",ans);  
}

int main()
{
  readdata();
  work();
  return 0;
}