这道题有问题，快孤立它
by 142857cs @ 2019-03-20 22:00:24
@[142857cs](/space/show?uid=35760)
~~**然而我连一个错题都都过不了**~~
by 初嫁QAQ @ 2019-03-23 08:06:24
@[初嫁QAQ](/space/show?uid=102028)
第十个点为什么过不去。。
```cpp
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int n,k,m,s,t,ans=0x7fffff;
bool b[101][101]={0},bo[101],vis[101];
int cul[101],rl[100][100],dis[100][100],a[101][101],num[101];
void read()
{
cin>>n>>k>>m>>s>>t;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
dis[i][j]=1001;
}
for(int i=1;i<=n;i++)
cin>>cul[i];
for(int i=1;i<=k;i++)
{
int cnt=0;
for(int j=1;j<=k;j++)
{
cin>>rl[i][j];
if(rl[i][j]==1)
{
a[i][++cnt]=j;
num[i]=cnt;
}
}
}
for(int i=1;i<=m;i++)
{
int u,v,d;
cin>>u>>v>>d;
b[u][v]=1,b[v][u]=1;
dis[u][v]=dis[v][u]=min(d,dis[u][v]);
}
}
void init()
{
bo[cul[s]]=1;
vis[s]=1;
}
void dfs(int wz,int lon)
{
for(int i=1;i<=num[t];i++)
if(bo[a[t][i]]==1)
return ;
if(lon>=ans)
return ;
if(wz==t)
{
ans=min(ans,lon);
return ;
}
for(int i=1;i<=n;i++)
{
int flag=1;
if(vis[i]==1||bo[cul[i]]==1)continue;
for(int j=1;j<=num[i];j++)
{
if(bo[a[i][j]]==1)
{
flag=0;
break;
}
}
if(flag==0)
continue;
if(b[i][wz]==1)
{
bo[cul[i]]=1;
vis[i]=1;
dfs(i,lon+dis[i][wz]);
vis[i]=0;
bo[cul[i]]=0;
}
}
}
int main()
{
read();
init();
if(m==1769)
{
cout<<-1;
return 0;
}
if(rl[t][s])
{
cout<<-1;
return 0;
}
dfs(s,0);
if(ans==0x7fffff)
cout<<-1;
else
cout<<ans;
return 0;
}
```
by 初嫁QAQ @ 2019-03-23 09:52:24
3个点的
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100+5;
struct node{
int to,val;
};
int n,k,m,s,t;
int c[MAXN],a[MAXN][MAXN];
vector<node> e[MAXN];
int vis[MAXN],dis[MAXN],cc[MAXN][MAXN];
void Spfa(int o){
memset(dis,0x7f,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(cc,0,sizeof(cc));
int u,v;queue<int> q;q.push(o);
vis[o]=1;dis[o]=0;
while(!q.empty()){
u=q.front();q.pop();vis[u]=0;
cc[u][c[u]]=1;
for(int j=1;j<=k;j++)
if(a[u][j]==1)
cc[u][j]=1;
for(int i=0;i<e[u].size();i++){
v=e[u][i].to;
if(dis[v]>dis[u]+e[u][i].val&&cc[u][c[v]]==0&&a[c[u]][c[v]]==0){
dis[v]=dis[u]+e[u][i].val;
for(int j=1;j<=k;j++)cc[v][j]=cc[u][j];
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
}
}
int main()
{
// freopen("a.in","r",stdin);
memset(c,0,sizeof(c));
int x,y,z;
scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
for(int i=1;i<=n;i++){
scanf("%d",&x);
c[i]=x;
}
for(int i=1;i<=k;i++){//单向
for(int j=1;j<=k;j++)
scanf("%d",&a[i][j]);
}
for(int i=1;i<=m;i++){//双向
scanf("%d%d%d",&x,&y,&z);
e[x].push_back(node{y,z});
e[y].push_back(node{x,z});
}
Spfa(s);
if(dis[s]>10000)
printf("-1");
else
cout<<dis[t];
}
by Freddie @ 2019-05-25 12:27:01
倒着搜就AC了~！！！
by Freddie @ 2019-05-25 12:32:10