初学图论, 其实还是dp的知识( 因为学校算法课讲dp讲到了floyd等算法 这道题目坑了还挺久的 毕竟第一次做这类型的题 于是记录记录~


Problem Description

虽然草儿是个路痴(就是在杭电待了一年多,居然还会在校园里迷路的人,汗~),但是草儿仍然很喜欢旅行,因为在旅途中 会遇见很多人(白马王子,^0^),很多事,还能丰富自己的阅历,还可以看美丽的风景……草儿想去很多地方,她想要去东京铁塔看夜景,去威尼斯看电影,去阳明山上看海芋,去纽约纯粹看雪景,去巴黎喝咖啡写信,去北京探望孟姜女……眼看寒假就快到了,这么一大段时间,可不能浪费啊,一定要给自己好好的放个假,可是也不能荒废了训练啊,所以草儿决定在要在最短的时间去一个自己想去的地方!因为草儿的家在一个小镇上,没有火车经过,所以她只能去邻近的城市坐火车(好可怜啊~)。

Input

输入数据有多组,每组的第一行是三个整数T,S和D,表示有T条路,和草儿家相邻的城市的有S个,草儿想去的地方有D个;
接着有T行,每行有三个整数a,b,time,表示a,b城市之间的车程是time小时;(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数,表示和草儿家相连的城市;
接着的第T+2行有D个数,表示草儿想去地方。

Output

输出草儿能去某个喜欢的城市的最短时间。

Sample Input

6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10

Sample Output

9


这道题在遇到问题后去搜索的时候, 发现很多人都是用dijkstra算法做的 但我还没学到这个, 而且作业是要我用floyd做这道题目.. 等过阵子学了dijkstra再回来试试(

跑题了 回到这个题目, 这道题一开始草儿是在他自己的家上. 可以当作为0号点, 题目描述的最后一句说到

因为草儿的家在一个小镇上,没有火车经过,所以她只能去邻近的城市坐火车(好可怜啊~)

题目也列出了小草能够去的邻近城市, 并且没有说要耗多少时间. 那么就说明从0到这些邻近城市的车程时间是0. 求去某个喜欢的城市的最短时间, 也就是求这些邻近城市点分别到喜欢的城市的最短路径(也就是单源最短路径 把每个邻近点当作起点 每个喜欢的城市当作终点 也是为什么这道题更多人用dijkstra做的原因)

那么回到正片, 也就是Floyd. 说说我一开始做这道题所犯得问题. 最初初始化这个代价矩阵的时候 是全部初始化成最大值的. (这道题全部初始化成最大值也行,后来做的一题不行 后面的文章会讲). wa, 改成下面这样

for(int i = 1;i <= 1000;i ++)
        {
            for(int j = 1;j <= 1000;j ++)
            {
                if(i == j)
                {
                    arc[i][j] = 0;
                }
                else
                {
                    arc[i][j] = 99999999;
                }
            }
        }

也还是wa. 于是继续对比后面的代码.发现也没啥差别(那时候看了一篇别人的题解).. 弄了很久还是wa后, 我尝试提交那位题解的代码上去 结果发现也是wa… (这tm真是绝了) 找了个正确的题解以后对比发现问题是在读入路径的权上出了问题.

//这是最初的代码 错误的问题在于读入路径权
 for(int i = 0;i < t;i ++)
        {
            int a = read(),b = read(), c = read();
            arc[a][b] = c;

            if(a > count || b > count)
            {
                count = a>b?a:b;
            }
        }
// 正确的代码
// 原因是
1.两个城市来回所花的时间是一样的 也就是是双向边
因此在读入arc[i][j]这条边的权值后 还要赋给arc[j][i]
2.数据有坑 有可能出现下面这种读入情况
3 4 3
4 3 8
那么8就会覆盖掉之前的3
经测试这两点去掉任何一点都会WA
for(int i = 0;i < t;i ++)
        {
            int a = read(),b = read(), c = read();
            if(arc[a][b] > c)
            {
                arc[a][b] = c;
                arc[b][a] = c; // key
            }
            count = max(count,max(a,b));
        }

在我原来的代码上处理了这两种情况后就ac了, 但同时要注意这道题目如果照写模版是会超时的. 因为数据范围是1000 1000的^3大概不用多说 因此要做以下优化


1.因为读入没有直接告诉一共有多少个城市 只是说明有多少条路 所以在读入边的时候 用一个变量记录最大的城市序号(这样就能得知有多少个城市 后面就不用全部遍历1000了 节省很多时间)

2.在跑Floyd的时候 在i循环的那里加一个判断 只有arc[i][k]这条路是能走的时候才进行j循环 这样能减少很多遍j循环

3.同时把赛选最小值的运算放到Floyd中 a数组用来存放邻近城市 b数组用来存放喜爱的城市,arc[i][j]求的是i到j的最短路径不用多说 那么判断一下i是否是出发点 j是否是终点 然后判断最小值即可. (应该也可以把最小值的计算放到外面弄一个两层循环 但是没试过是否会超时

for(int i = 1;i <= count;i ++)
     if(arc[i][k] != 99999999)
     {
         for(int j = 1;j <= count;j ++)
         {
            if(arc[i][k] + arc[k][j] < arc[i][j])
            {
                 arc[i][j] = arc[i][k] + arc[k][j];
            }
            if(a[i] && b[j])
            {
                ans = min(ans,arc[i][j]);
            }
         }
     }
}

完整代码

#include <stdio.h>
#include <algorithm>
using namespace std;
int read()
{
    char ch = getchar();
    int f = 1;
    int x = 0;
    while(ch < '0' || ch > '9'){if(ch == '-')f = 0;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return f?x:x*-1;
}
int main()
{
    int t,s,d;

    while(scanf("%d %d %d",&t,&s,&d) != EOF)
    {
        int arc[1001][1001] = {};
        for(int i = 1;i <= 1000;i ++)
        {
            for(int j = 1;j <= 1000;j ++)
            {
                if(i == j)
                {
                    arc[i][j] = 0;
                }
                else
                {
                    arc[i][j] = 99999999;
                }
            }
        }
        int count = 0;
        for(int i = 0;i < t;i ++)
        {
            int a = read(),b = read(), c = read();
            if(arc[a][b] > c)
            {
                arc[a][b] = c;
                arc[b][a] = c; // key
            }
            count = max(count,max(a,b));
        }

        int a[1001] = {};
        for(int i = 0;i < s;i ++)
        {
            int t = read();
            a[t] = 1;
        }
        int b[1001] = {};
        for(int i = 0;i < d;i ++)
        {
            int t = read();
            b[t] = 1;
        }

        int ans = 99999999;
        for(int k = 1;k <= count;k ++)
        {
            for(int i = 1;i <= count;i ++)
            {
                if(arc[i][k] != 99999999)
                {
                    for(int j = 1;j <= count;j ++)
                    {
                        if(arc[i][k] + arc[k][j] < arc[i][j])
                        {
                            arc[i][j] = arc[i][k] + arc[k][j];
                        }
                        if(a[i] && b[j])
                        {
                            ans = min(ans,arc[i][j]);
                        }
                    }
                }
            }
        }

        printf("%d\n",ans);
    }

    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

OIer

并查集学习总结

并查集学习总结 并查集在好早之前就想学了.. 虽然是一种比较简单的数据 Read more…

OIer

归并排序学习总结 & P1309

背景 之所以突然说到归并排序,是因为P1309这道题要用到&#8230 Read more…

OIer

队列和广度优先搜索

队列(queue) 队列是什么 队列是一种特殊的线性表. 是一种先进先 Read more…