NOIP 2012 普及组 复赛 culture 文化之旅

NOip 2012 普及组 复赛 culture 文化之旅

1.找寻迪杰斯特拉(Dijkstra)算法，难度适中，过程中，找到该题。

2.结合题意，弄懂输入输出样例是关键一步。

3.为了能解决2，纸笔是必须的。

4.读该题样例输入部分，感觉有点象栈，需要相当的记忆。编程，对锻炼大脑，栈的记忆，有很大作用。

5.该题的数据比较水，n<=100,n^2<=10000，所以超时一般不会。

6.该题可以看作有条件约束的最短路径。

7.该题的难想之处，在于将aij=1转化为，两国之间路径为INF。

8.可采用Dijkstra算法，但Floyd算法写起来更简单。

9.因其起点，终点位置未定，故综合考虑，采用Floyd算法。

10.此题需注意的一句：距离为 d 的可双向通行的道路。请注意双向两字。

11.还有一句需注意：aij= 1 表示文化 i 排斥外来文化 j。请注意外来两字。

12.该题需注意，一番数据处理后，还是回归基本的最短路径问题。

附上AC代码，编译环境Dev-C++4.9.9.2

#include <stdio.h>#define INF 999999int main(){    int n,k,m,s,t;    int c[100+10];    int a[100+10][100+10];    int e[100+10][100+10];    int i,j,q;    int u,v,w;    scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);    for(i=1;i<=n;i++)        scanf("%d",&c[i]);    for(i=1;i<=k;i++)        for(j=1;j<=k;j++)            scanf("%d",&a[i][j]);    for(i=1;i<=n;i++)        for(j=1;j<=n;j++){            if(i==j)                e[i][j]=0;            else                e[i][j]=INF;        }    for(i=1;i<=m;i++){        scanf("%d%d%d",&u,&v,&w);        e[u][v]=w;        e[v][u]=w;    }    for(i=1;i<=n;i++)        for(j=1;j<=n;j++)            if(i!=j&&a[c[j]][c[i]]==1)                e[i][j]=INF;    for(q=1;q<=n;q++)        for(i=1;i<=n;i++)            for(j=1;j<=n;j++)                if(e[i][j]>e[i][q]+e[q][j])                    e[i][j]=e[i][q]+e[q][j];    if(e[s][t]<INF)        PRintf("%d/n",e[s][t]);    else        printf("-1/n");    return 0;}