好强啊

记忆化搜索无压力秒杀全过！！！
全测试数据 #0: Accepted, time = 15 ms, mem = 940 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 940 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 940 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 944 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 940 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 940 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 940 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 944 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 940 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 944 KiB, score = 10
Accepted, time = 60 ms, mem = 944 KiB, score = 100
procedure so(u,uu:longint);
var i,j,k:longint;
begin
for i:=1 to count[u] do
if (uu<>wen[s[u,i]])and(b[wen[s[u,i]],uu]=0)then
if dis[u]+f[u,s[u,i]]<dis[s[u,i]]
then begin
dis[s[u,i]]:=dis[u]+f[u,s[u,i]];
so(s[u,i],wen[s[u,i]]);
end;
end;
记得一年前比赛题目都看不懂，现在写个搜索都能过了！
一年后的我变强了，冲刺NOIP！！！

测试数据 #0: Accepted, time = 0 ms, mem = 912 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 912 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 912 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 920 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 912 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 912 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 912 KiB, score = 10

测试数据 #7: Accepted, time = 343 ms, mem = 916 KiB, score = 10

测试数据 #8: Accepted, time = 312 ms, mem = 912 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 916 KiB, score = 10

var
culture,num,now:array[0..100] of longint;
no:array[0..100,0..100] of boolean;
visit:array[0..100] of boolean;
map,go:array[0..100,0..100] of longint;
ans,s,t,dis,h,n,j,kk,m,i,u,v,d,ch:longint;
procedure try(k:longint);
var
i,p,j,culture_now:longint;
pop,temp:boolean;
begin
if dis>ans then exit;
if k=s then
begin
ans:=dis;
exit;
end;
for i:=num[k] downto 1 do
begin
p:=go[k,i];
if (visit[p]) then
begin
pop:=true;
culture_now:=culture[p];
for j:=1 to h do
if no[culture_now,now[j]] then
begin
pop:=false;
break;
end;
if not(pop) then continue;
inc(h);
now[h]:=culture_now;
dis:=dis+map[k,p];
visit[p]:=false;
try(p);
dis:=dis-map[k,p];
visit[p]:=true;
dec(h);
end;
end;
end;
begin
{assign(input,'culture.in');
assign(output,'culture.out');
reset(input);
rewrite(output); }

readln(n,kk,m,s,t);
for i:=1 to n do
read(culture[i]);
for i:=1 to kk do
begin
for j:=1 to kk do
begin
read(ch);
if (ch=1) or (i=j) then no[i,j]:=true;
end;
readln;
end;
fillchar(map,sizeof(map),$7f);
fillchar(visit,sizeof(visit),true);
fillchar(now,sizeof(now),false);
for i:=1 to m do
begin
readln(u,v,d);
map[u,v]:=d;
map[v,u]:=d;
inc(num[u]);
go[u,num[u]]:=v;
inc(num[v]);
go[v,num[v]]:=u;
end;
visit[t]:=false;
h:=1;
now[1]:=culture[t];
ans:=maxlongint;
dis:=0;
try(t);
if ans=maxlongint then writeln(-1) else writeln(ans);

{close(input);
close(output); }
end.
大家注意，只要把目的地和出发地、邻接表顺序全都相反即可

用dijkstra怎么样

哦呵呵呵呵呵呵~~~数据好弱= =
裸SPFA都90

来个pascal 版
var
n,k,m,s,t,i,j,u,v,d,a:longint;
f:array[0..1001,0..1001] of boolean;
mp:array[0..1001,0..1001] of longint;
cu:array[0..1001] of longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a)
else exit(b);
end;
begin
readln(n,k,m,s,t);
for i:=1 to n do
read(cu[i]);
fillchar(f,sizeof(f),false);
for i:=1 to k do
for j:=1 to k do
begin
read(a); if a=1 then f[i,j]:=true;
end;
for i:=1 to n do
for j:=1 to n do
mp[i,j]:=100000;
for i:=1 to m do
begin
readln(u,v,d);
if not(f[cu[v],cu[u]]) then mp[u,v]:=min(mp[u,v],d);
if not(f[cu[u],cu[v]]) then mp[v,u]:=min(mp[v,u],d);
end;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if not(f[cu[j],cu[i]]) then
mp[i,j]:=min(mp[i,j],mp[i,k]+mp[k,j]);
if mp[s,t]=100000 then writeln('-1')
else writeln(mp[s,t]);
end.

Floyd水过~
VijosEx via JudgeDaemon2/13.6.5.0 via libjudge
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 500 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 492 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 496 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 500 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 500 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 500 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 496 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 500 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 496 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 500 KiB, score = 10
Accepted, time = 45 ms, mem = 500 KiB, score = 100
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAXN 110
#define MAX 1000000

int map[MAXN][MAXN];
int cult[MAXN];
bool f[MAXN][MAXN];
int n,m,k,s,t;

int main(){
scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
for (int i=0;i++<n;){
scanf("%d",&cult[i]);
}
memset(f,true,sizeof(f));
for (int i=0;i++<k;){
for (int j=0;j++<k;){
int x;
scanf("%d",&x);
if (i==j){
f[i][j]=false;
} else if (x) {
f[j][i]=false;
}
}
}
for (int i=0;i++<n;){
for (int j=0;j++<n;){
map[i][j]=MAX;
}
}
while (m--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if (f[cult[x]][cult[y]]){
map[x][y]=min(map[x][y],z);
}
}
for (int h=0;h++<n;){
for (int i=0;i++<n;){
for (int j=0;j++<n;){
if (f[cult[i]][cult[j]]){
map[i][j]=min(map[i][j],map[i][h]+map[h][j]);
}
}
}
}
if (map[s][t]<MAX) printf("%d\n",map[s][t]);
else printf("-1\n");
return 0;
}

怎么一眼看上去是最短路。。。。。

这题输出-1能骗10分

嘻嘻

模拟过

预处理+SPFA
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int cul[1000];
int dis[1000];
int q[1000];
int rel[1000][1000];
int road[1000][1000];
int f[1000][1000];
bool vis[1000];
const int INF = 100000000;
int main()
{
int n, k, m, s, c, x, y, z;
cin >> n >> k >> m >> s >> c;
for (int i = 1;i <= n;i++)
scanf("%d", &cul[i]);
for (int i = 1;i <= k;i++)
for (int j = 1;j <= k;j++)
scanf("%d", &rel[i][j]);
for (int i = 1;i <= m;i++)
{
scanf("%d%d%d", &x, &y, &z);
if (cul[x] == cul[y]) continue;
if (rel[cul[y]][cul[x]] == 0)
{
f[x][y] = z;
road[x][++road[x][0]] = y;
}
if (rel[cul[x]][cul[y]] == 0)
{
f[y][x] = z;
road[y][++road[y][0]] = x;
}
}
for (int i = 1;i <= n;i++) dis[i] = INF;
dis[s] = 0;
int h = 0;
int t = 1;
q[1] = s;
vis[s] = true;
while (h < t)
{
h++;int i = q[h];
for (int j = 1;j <= road[i][0];j++)
{
int k = road[i][j];
if (dis[k] > dis[i] + f[i][k])
{
dis[k] = dis[i] + f[i][k];
if (!vis[road[i][j]])
{
vis[road[i][j]] = true;
t++;
q[t] = road[i][j];
}
}
}
vis[i] = false;
}
if (dis[c] == INF)
cout << "-1" << endl;
else cout << dis[c] << endl;
}

Floyd最短路。
查了半天的RE发现读入文化排斥时写成1..n 1..n循环了..
话说这题要搜索吗?

C

//C99
#include<stdio.h>
#include<stdlib.h>
#define INF 0xffffff
int n,k,m,s,t,c[202],f[202][202];
_Bool a[202][202];
void main(){
    scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
    for(int i=1;i<=n;i++)
    scanf("%d",&c[i]);
    for(int i=1;i<=k;i++)
    for(int j=1;j<=k;j++)
    scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    f[i][j]=INF;
    for(int i=1;i<=m;i++){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        if(f[u][v]>d)
        f[u][v]=f[v][u]=d;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(a[c[i]][c[j]])f[i][j]=INF;
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    //if(i!=k)
    for(int j=1;j<=n;j++)
    //if(i!=j&&j!=k)
    if(f[i][j]>f[i][k]+f[k][j])f[i][j]=f[i][k]+f[k][j];
    if(f[t][s]==INF)f[t][s]=-1;
    printf("%d\n",f[t][s]);
    exit(0);
}