题解 P1811 【最短路_NOI导刊2011提高(01)】

2017-05-22 21:15:10


1.对于每一个三元组来说,不存在用两条边重复的情况

所以不需要复杂的判断,只用一个数组f[x][y]来表示经过x y不可以到达的值即可

2.这题应为要记录下路径,所以选用了bfs来写,每次记录一个father[]来表示从那一个节点来,在找到最短路后用dfs逆序输出即可


#include <stdio.h>
#define maxn 3001
#define p 100000
using namespace std;
int t[p],father[p],state[p];
bool a[maxn][maxn];
int f[maxn][maxn];
int i,j,k,m,n,s,x,y,z,min;
int l=0,xx[maxn];
int dfs(int dep)
{
    if (dep == 0) return 0;
    xx[++l]=t[dep];
    dfs(father[dep]);
}
int bfs()
{
    int head=0,tail=1,i,j;
    t[1]=1;
    father[1]=0;
    state[1]=0;
    while (head<=tail)
    {
        head++;
        for (i=1;i<=n;i++)
            if (a[t[head]][i]&&f[t[father[head]]][t[head]]!=i&&i!=t[head])
            {
                tail++;
                t[tail]=i;
                state[tail]=state[head]+1;
                father[tail]=head;
                if (i==n)
                {
                    dfs(tail);
                    min=state[tail];
                    return 0;
                }
            }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for (i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        a[x][y]=true;
        a[y][x]=true;
    }
    for (i=1;i<=k;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        f[x][y]=z;
    }
    bfs();
    printf("%d\n",min);

    for (int i = l; i >= 1; i--)
        printf("%d ", xx[i]);
    return 0;
}