鱼C论坛

 找回密码
 立即注册
查看: 41|回复: 1

[学习笔记] 028:最短路径问题

[复制链接]
最佳答案
17 
发表于 2018-2-13 16:25:49 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Messj 于 2018-6-8 23:41 编辑

Problem Description
给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。


Input
输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)


Output
输出 一行有两个数, 最短距离及其花费。


Sample Input
3 2  1 2 5 6  2 3 4 5  1 3  0 0


Sample Output
9 11

题目解析:注意两点
1、去掉重复的路径,选择较短的。读入重时时如果路径长度相同,则选择花费较小的。
2、不能用记录路径然后回溯的方法求最小花费,因为如果某两点之间有多条路径相等,则路径只能记录一种,不能根据此得出花费,应该先按照路径松弛,如果路径相等的话按照花费松弛!

本帖被以下淘专辑推荐:

最佳答案
17 
 楼主| 发表于 2018-2-13 16:27:28 | 显示全部楼层
点的数目远远超过200,Floyd算法的时间复杂度就超过了千万级别。因此只能使用dijkstra算法

  1. #include<cstdio>
  2. #include<vector>
  3. #define N 1001

  4. using namespace std;

  5. struct E
  6. {
  7.         int next;
  8.         int c;
  9.         int cost;
  10. };
  11. vector<E> edge[N];
  12. bool mark[N];
  13. int dis[N];
  14. int cost[N];
  15. int main()
  16. {
  17.         int n,m;
  18.         int S,T;
  19.         while(scanf("%d%d",&n,&m)!=EOF)
  20.         {
  21.                 if(n==0&&m==0)        break;
  22.                 for(int i=1;i<=n;i++)        edge[i].clear();
  23.                 while(m--)
  24.                 {
  25.                         int a,b,c,cost;
  26.                         scanf("%d%d%d%d",&a,&b,&c,&cost);
  27.                         E tmp;
  28.                         tmp.c=c;
  29.                         tmp.cost=cost;
  30.                         tmp.next=b;
  31.                         edge[a].push_back(tmp);
  32.                         tmp.next=a;
  33.                         edge[b].push_back(tmp);
  34.                 }
  35.                 scanf("%d%d",&S,&T);
  36.                 for(int i=1;i<=n;i++)
  37.                 {
  38.                         dis[i]=-1;
  39.                         mark[i]=false;
  40.                 }
  41.                 dis[S]=0;
  42.                 cost[S]=0;
  43.                 mark[S]=true;        //点1加入集合
  44.                 int newP=S;                //新加入集合的点为点1
  45.                 for(int i=1;i<n;i++)
  46.                 {
  47.                         for(int j=0;j<edge[newP].size();j++)
  48.                         {
  49.                                 int t=edge[newP][j].next;
  50.                                 int c=edge[newP][j].c;
  51.                                 int co=edge[newP][j].cost;
  52.                                 if(mark[t]==true)        continue;
  53.                                 if(dis[t]==-1||dis[t]>(dis[newP]+c||dis[t]==dis[newP]+c&&cost[t]>cost[newP]+co))
  54.                                 {
  55.                                         dis[t]=dis[newP]+c;
  56.                                         cost[t]=cost[newP]+co;
  57.                                 }
  58.                         }
  59.                         int min=123123123;
  60.                         for(int j=1;j<=n;j++)
  61.                         {
  62.                                 if(mark[j])        continue;
  63.                                 if(dis[j]==-1)        continue;
  64.                                 if(dis[j]<min)
  65.                                 {
  66.                                         min=dis[j];
  67.                                         newP=j;
  68.                                 }
  69.                         }
  70.                         mark[newP]=true;
  71.                 }
  72.                 printf("%d %d\n",dis[T],cost[T]);
  73.         }
  74. }
复制代码
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号

GMT+8, 2018-8-16 14:32

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表