• 1030 Travel Plan

    A traveler's map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.

    Input Specification:

    Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (≤500) is the number of cities (and hence the cities are numbered from 0 to N−1); M is the number of highways; S and D are the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format:

    City1 City2 Distance Cost

    where the numbers are all integers no more than 500, and are separated by a space.

    Output Specification:

    For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.

    Sample Input:

    1. 4 5 0 3
    2. 0 1 1 20
    3. 1 3 2 30
    4. 0 3 4 10
    5. 0 2 2 20
    6. 2 3 1 20

    Sample Output:

    0 2 3 3 40

    题目大意

    求无向图中，某两点间最短距离且权重最小的路径

    思路

    暴力动规 or 帝洁磕四

    C/C++  （暴力动规）

    1. #include
    2. using namespace std;
    3. vector<int> road[501],key,result;
    4. int N,M,st,ed,len[501][501],cost[501][501],lenKey=99999999,costKey;
    5. void findRoad(int now,int sumLen,int sumCost);
    6. int main()
    7. {
    8.     int a,b,c,d;
    9.     cin >> N >> M >> st >> ed;
    10.     while (M--){
    11.         cin >> a >> b >> c >> d;
    12.         road[a].push_back(b);
    13.         road[b].push_back(a);
    14.         len[a][b] = len[b][a] = c;
    15.         cost[a][b] = cost[b][a] = d;
    16.     }
    17.     findRoad(st,0,0);
    18.     for(int x:result) cout << x << " ";
    19.     cout << ed << " " << lenKey << " " << costKey;
    20.     return 0;
    21. }
    22. bool apr[501];
    23. void findRoad(int now,int sumLen,int sumCost)
    24. {
    25.     if(apr[now] || sumLen>lenKey) return;
    26.     if(now==ed){
    27.         if(sumLen
    28.             lenKey = sumLen;
    29.             costKey = sumCost;
    30.             result.assign(key.begin(),key.end());
    31.         }
    32.  
    33.         return;
    34.     }
    35.     apr[now] = true;
    36.     key.push_back(now);
    37.     for(int x:road[now]) findRoad(x,sumLen+len[now][x],sumCost+cost[now][x]);
    38.     key.pop_back();
    39.     apr[now] = false;
    40. }

    C/C++ (Dijkstra)

    1. #include
    2. using namespace std;
    3. int N,M,road[501][501],cost[501][501],edC,st,ending;
    4. int ed[501],last[501],edCost[501];
    5. void Dijkstra(){
    6.     memset(ed,0x3f,sizeof ed);
    7.     memset(edCost,0,sizeof edCost);
    8.     last[st] = -1;
    9.     ed[st] = 0;
    10.     bool apr[501] = {false};
    11.     for(int z=0;z
    12.         int key = -1;
    13.         for(int z1=0;z1
    14.             if(!apr[z1] && (key==-1 || ed[z1]
    15.         }
    16.         apr[key] = true;
    17.         for(int z1=0;z1
    18.             int len = ed[key]+road[key][z1];
    19.             int money = edCost[key] + cost[key][z1];
    20.             if(ed[z1]>len || (ed[z1]==len && edCost[z1]>money)){
    21.                 ed[z1] = len;
    22.                 last[z1] = key;
    23.                 edCost[z1] = money;
    24.             };
    25.         }
    26.     }
    27. }
    28. void print(int now){
    29.     if(now!=-1) print(last[now]);
    30.     else return;
    31.     printf("%d ",now);
    32.     if(now==ending) printf("%d %d",ed[now],edCost[now]);
    33. }
    34. int main()
    35. {
    36.     memset(road,0x3f,sizeof road);
    37.     cin >> N >> M >> st >> ending;
    38.     while (M--){
    39.         int a,b,c,d;
    40.         cin >> a >> b >> c >> d;
    41.         road[a][b] = road[b][a] = c;
    42.         cost[a][b] = cost[b][a] = d;
    43.     }
    44.     Dijkstra();
    45.     print(ending);
    46.     return 0;
    47. }

  • 相关阅读:
    centos8常见报错处理
    Qt语法
    设计原则——合成复用原则
    电脑e盘文件没删除但不见了怎么办？了解原因与找回方法
    查询中一些字段的用法
    【开题报告】基于uni-app的汽车租赁app的设计与实现
    三、双指针（two-point）
    【6 - 完结】Sql Server - 郝斌（identity、视图、事务、索引、存储过程、触发器、游标、TL_SQL）
    贪心算法学习——最长单调递增子序列
    [最新]访问/加速StackOverFlow的方法
  • 原文地址：https://blog.csdn.net/daybreak_alonely/article/details/127720641