首页 > 代码库 > 最短路径问题分数: 3.5

最短路径问题分数: 3.5

2024-11-24 14:08:39   203人阅读

 

时间限制：1 秒
内存限制：32 兆
特殊判题： 否
提交：62
解决： 28

标签

  • 最短路径

题目描述

 

 

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

 

输入格式

 

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

 

 

输出

 

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

 

 

样例输入

3 2
1 2 5 6
2 3 4 5
1 3
0 0

样例输出

9 11

提示[+]

*** 提示已隐藏，点击上方 [+] 可显示 ***

分类

  • 浙江大学研究生复试上机真题
  •  
  •  
  •  
  •  
  • max min 在OJ  c++都是保留字 函数名，在6.0里面可以编译通过，但是OJ上就不行!!!
  •  
  •  1 #include<iostream> 2 #include<string> 3 using namespace std; 4 const int inf=10000000;  5 struct graph  //节点 6 { 7    int len; 8    int cost; 9 }g[1001][1001],min1[1001];//g为图的连接矩阵，min存起点到个个点的最短距离和最少花费10 void dijkstr(int n,int s)//n 节点个数 ，s起点编号11 {12 //初始化13     int v[1001]={0};//v[i]=0 表示还没并入路径中；14      for(int j=1;j<=n;j++)15  {16     min1[j].len=inf;17 min1[j].cost=inf;18  }19      min1[s].len=0;20  min1[s].cost=0;21  for(int x=1;x<=n;x++)22  {23          int MIN=inf;//最小路长24  int pri=inf;//最小费用25  int u;26      for(int y=1;y<=n;y++)//选最小的节点并入27  {28     if(v[y]==0&&((MIN>min1[y].len)||(MIN==min1[y].len&&pri>min1[y].cost)))29 {30    u=y;31    MIN=min1[y].len;32    pri=min1[y].cost;33 }34  }35  v[u]=1;  36  for(int z=1;z<=n;z++)  //更新u并入后的个个min的值37  {38     if(v[z]==0&&((min1[u].len+g[u][z].len<min1[z].len)||((min1[u].len+g[u][z].len==min1[z].len)&&(min1[u].cost+g[u][z].cost<min1[z].cost))))39 {40   min1[z].len=min1[u].len+g[u][z].len;41   min1[z].cost=min1[u].cost+g[u][z].cost;42 }43  }44  }45 }46 int main()47 {48 int n;49 while(cin>>n)50 {51 //初始化52 for(int j=1;j<=n;j++)53         for(int k=1;k<=n;k++)54 {55   g[j][k].len=inf;56                 g[k][j].cost=inf;57 }58 int m;59    cin>>m;60    if(n==0&&m==0)  break;61    for(int i=1;i<=m;i++)62    {63    int a,b,d,p;64       cin>>a>>b>>d>>p;65    g[a][b].len=d;66    g[a][b].cost=p;67    g[b][a].len=d;68    g[b][a].cost=p;69    }70    int s,t;71    cin>>s>>t;72    dijkstr(n,s);73        cout<<min1[t].len<<" "<<min1[t].cost<<endl;74 }75  return 0;76 }77

     

最短路径问题分数: 3.5


联系
我们