1111 Online Map (PAT甲级)

这篇具有很好参考价值的文章主要介绍了1111 Online Map (PAT甲级)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

这道题我读题不仔细导致踩了个大坑,一个测试点过不了卡了好几个小时:第二个dijkstra算法中,题目要求是“In case the fastest path is not unique, output the one that passes through the fewest intersections”,我却想当然地认为在fastest path is not unique的时候,判断标准是最短距离……

#include <cstdio>
#include <vector>
#include <algorithm>
const int MAXN = 501;
const int INF = 999999999;

int N, M, u, v, oneWay, a, b, src, dst, tmp;
int dist[MAXN][MAXN];
int time[MAXN][MAXN];
int path[MAXN];
std::vector<int> d1, t1, t2, path1, path2;

void dijkstra1(int k){
    int minDist, pivot;
    d1.resize(N, INF);
    t1.resize(N, INF);
    std::vector<bool> visited(N);
    std::fill(visited.begin(), visited.end(), false);
    std::fill(path, path + N, -1);
    d1[k] = 0;
    t1[k] = 0;
    for(int i = 0; i < N; ++i){
        pivot = -1;
        minDist = INF;
        for(int j = 0; j < N; ++j){
            if(!visited[j] && d1[j] < minDist){
                pivot = j;
                minDist = d1[j];
            }
        }
        if(pivot == -1){
            return;
        }
        visited[pivot] = true;
        for(int j = 0; j < N; ++j){
            if(!visited[j] && dist[pivot][j] < INF && d1[pivot] + dist[pivot][j] < d1[j]){
                d1[j] = d1[pivot] + dist[pivot][j];
                t1[j] = t1[pivot] + time[pivot][j];
                path[j] = pivot;
            } else if(!visited[j] && dist[pivot][j] < INF && time[pivot][j] < INF
                && d1[pivot] + dist[pivot][j] == d1[j] && t1[pivot] + time[pivot][j] < t1[j]){
                t1[j] = t1[pivot] + time[pivot][j];
                path[j] = pivot;
            }
        }
    }
}

void dijkstra2(int k){
    int minTime, pivot;
    t2.resize(N, INF);
    std::vector<int> intersection(N, INF);
    std::vector<bool> visited(N);
    std::fill(visited.begin(), visited.end(), false);
    std::fill(path, path + N, -1);
    intersection[k] = 0;
    t2[k] = 0;
    for(int i = 0; i < N; ++i){
        pivot = -1;
        minTime = INF;
        for(int j = 0; j < N; ++j){
            if(!visited[j] && t2[j] < minTime){
                pivot = j;
                minTime = t2[j];
            }
        }
        if(pivot == -1){
            return;
        }
        visited[pivot] = true;
        for(int j = 0; j < N; ++j){
            if(!visited[j] && time[pivot][j] < INF && t2[pivot] + time[pivot][j] < t2[j]){
                t2[j] = t2[pivot] + time[pivot][j];
                intersection[j] = intersection[pivot] + 1;
                path[j] = pivot;
            } else if(!visited[j] && time[pivot][j] < INF
                && t2[pivot] + time[pivot][j] == t2[j] && intersection[pivot] + 1 < intersection[j]){
                intersection[j] = intersection[pivot] + 1;
                path[j] = pivot;
            }
        }
    }
}

int main(){
    std::fill(dist[0], dist[0] + MAXN * MAXN, INF);
    std::fill(time[0], time[0] + MAXN * MAXN, INF);
    scanf("%d %d", &N, &M);
    for(int i = 0; i < M; ++i){
        scanf("%d %d %d %d %d", &u, &v, &oneWay, &a, &b);
        dist[u][v] = a;
        time[u][v] = b;
        if(!oneWay){
            dist[v][u] = a;
            time[v][u] = b;
        }
    }
    scanf("%d %d", &src, &dst);
    dijkstra1(src);
    tmp = dst;
    while(path[tmp] != -1){
        path1.push_back(tmp);
        tmp = path[tmp];
    }
    dijkstra2(src);
    tmp = dst;
    while(path[tmp] != -1){
        path2.push_back(tmp);
        tmp = path[tmp];
    }
    if(path1 == path2){
        printf("Distance = %d; Time = %d: %d", d1[dst], t1[dst], src);
        for(int i = path1.size() - 1; i >= 0; --i){
            printf(" -> %d", path1[i]);
        }
    } else{
        printf("Distance = %d: %d", d1[dst], src);
        for(int i = path1.size() - 1; i >= 0; --i){
            printf(" -> %d", path1[i]);
        }
        printf("\nTime = %d: %d", t2[dst], src);
        for(int i = path2.size() - 1; i >= 0; --i){
            printf(" -> %d", path2[i]);
        }
    }
    return 0;
}

题目如下:

Input our current position and a destination, an online map can recommend several paths. Now your job is to recommend two paths to your user: one is the shortest, and the other is the fastest. It is guaranteed that a path exists for any request.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (2≤N≤500), and M, being the total number of streets intersections on a map, and the number of streets, respectively. Then M lines follow, each describes a street in the format:

V1 V2 one-way length time

where V1 and V2 are the indices (from 0 to N−1) of the two ends of the street; one-way is 1 if the street is one-way from V1 to V2, or 0 if not; length is the length of the street; and time is the time taken to pass the street.

Finally a pair of source and destination is given.

Output Specification:

For each case, first print the shortest path from the source to the destination with distance D in the format:

Distance = D: source -> v1 -> ... -> destination

Then in the next line print the fastest path with total time T:

Time = T: source -> w1 -> ... -> destination

In case the shortest path is not unique, output the fastest one among the shortest paths, which is guaranteed to be unique. In case the fastest path is not unique, output the one that passes through the fewest intersections, which is guaranteed to be unique.

In case the shortest and the fastest paths are identical, print them in one line in the format:文章来源地址https://www.toymoban.com/news/detail-468927.html

Distance = D; Time = T: source -> u1 -> ... -> destination

Sample Input 1:

10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
3 4 0 3 2
3 9 1 4 1
0 6 0 1 1
7 5 1 2 1
8 5 1 2 1
2 3 0 2 2
2 1 1 1 1
1 3 0 3 1
1 4 0 1 1
9 7 1 3 1
5 1 0 5 2
6 5 1 1 2
3 5

Sample Output 1:

Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5

Sample Input 2:

7 9
0 4 1 1 1
1 6 1 1 3
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 1 3
3 2 1 1 2
4 5 0 2 2
6 5 1 1 2
3 5

Sample Output 2:

Distance = 3; Time = 4: 3 -> 2 -> 5

到了这里,关于1111 Online Map (PAT甲级)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 1114 Family Property (PAT甲级)

    This time, you are supposed to help us collect the data for family-owned property. Given each person\\\'s family members, and the estate(房产)info under his/her own name, we need to know the size of each family, and the average area and number of sets of their real estate. Input Specification: Each input file contains one test case. For each case, the fir

    2024年02月06日
    浏览(49)
  • 1028 List Sorting (PAT甲级)

    Excel can sort records according to any column. Now you are supposed to imitate this function. Input Specification: Each input file contains one test case. For each case, the first line contains two integers N (≤105) and C, where N is the number of records and C is the column that you are supposed to sort the records with. Then N lines follow, eac

    2024年02月15日
    浏览(39)
  • 1083 List Grades (PAT甲级)

    Given a list of N student records with name, ID and grade. You are supposed to sort the records with respect to the grade in non-increasing order, and output those student records of which the grades are in a given interval. Input Specification: Each input file contains one test case. Each case is given in the following format: where  name[i]  and  ID[i

    2024年02月08日
    浏览(48)
  • 1072 Gas Station (PAT甲级)

    A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible. However it must guarantee that all the houses are in its service range. Now given the map of the city and several candidate locations for the gas station, you are supposed to give the best recommendatio

    2024年02月09日
    浏览(40)
  • PAT甲级图论相关题目

    PAT甲级图论相关题目: 分数 25 As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some o

    2024年01月21日
    浏览(52)
  • 1021 Deepest Root (PAT甲级)

    1021. Deepest Root (25)-PAT甲级真题(图的遍历,dfs,连通分量的个数)_柳婼的博客-CSDN博客 柳婼的解法在这里,两次dfs,还是挺好玩的。 我的解法比较暴力,就是先用并查集算连通分量(这个其实还是dfs来算会更方便),如果只有一个连通分量,那deepest root一定在仅有一条arc的

    2024年02月15日
    浏览(32)
  • 1074 Reversing Linked List (PAT甲级)

    Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6. Input Specification: Each input file contains one test case. For each case, the first line

    2024年02月09日
    浏览(40)
  • PAT 甲级【1007 Maximum Subsequence Sum】

    本题是考察动态规划与java的快速输入: max[i]表示第i个结尾的最大的连续子串和。b begin[i]表示第[begin[i],i]为最大和的开始位置 超时代码: 未超时: 能用动态规划解决的问题,需要满足三个条件:最优子结构,无后效性和子问题重叠。 具有最优子结构也可能是适合用贪心的

    2024年02月08日
    浏览(38)
  • PAT 甲级1005【1005 Spell It Right】

    用JAVA可以用BigInteger解决。       太长不看版:结尾自取模板…… 高精度计算(Arbitrary-Precision Arithmetic),也被称作大整数(bignum)计算,运用了一些算法结构来支持更大整数间的运算(数字大小超过语言内建整型)。 高精度问题包含很多小的细节,实现上也有很多讲究。

    2024年02月08日
    浏览(84)
  • 菜鸟记录:c语言实现PAT甲级1010--Radix

    很长时间没做,忙于考研和实习,久违的的拾起了算法。做了很长时间,其实总体思路还是很简单的,但满分不知道为什么就是到不了,又因为网上很多答案包括柳神的都是c++,无法参透,姑且只能这样了。 Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 b

    2024年04月08日
    浏览(72)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包