Problem

给你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

Dijkstra算法：

有n个集合（初始有n个点，一个点独自成一个集合），先选出一条最短的边，假设它属于集合u，然后从跟它邻接的边中选出一条最短的且不与集合u中已经存在的边形成回路的边，合并到集合u中，再从非u集合中选出一条与集合u中的边邻接且距离最短的边，加入到集合u中，以此类推。

Dijkstra是用来解决给定起点和重点求路径的问题。

#include <iostream>
#include <queue>
#define INF 0x3f
using namespace std;
int Map[1005][1005];
int costMap[1005][1005];
int dist[1005];
int cost[1005];
int main()
{
int n,m;//超时原因是在这里定义了所有要用到的变量
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
memset(Map,0x3f,sizeof(Map));
//初始化距离邻接表，初始值为INF
memset(costMap,0x3f,sizeof(costMap));
//初始化花费邻接表，初始值为INF
memset(dist,0x3f,sizeof(dist));
//dist[i]表示点i到起点s的距离，初始值为INF
memset(cost,0x3f,sizeof(cost));
//cost[i]表示点i到起点s的花费，初始值为INF
for(int i=0;i<m;i++)
{
int a,b,d,p;
scanf("%d%d%d%d",&a,&b,&d,&p);
if(Map[a][b]>d)//如果a，b两点之间距离小于邻接表中的a，b距离
{
Map[a][b]=Map[b][a]=d;//更新距离邻接表
costMap[a][b]=costMap[b][a]=p;//更新花费邻接表
}
else if(Map[a][b]==d)//如果a，b两点之间距离等于邻接表中的a，b距离
{
costMap[a][b]=costMap[b][a]=min(costMap[a][b],p);//更新花费邻接表，取更小值
}
//优先考虑距离，距离相等的情况下考虑花费
}
int s,t;
cin>>s>>t;
dist[s]=cost[s]=0;//s到s的距离为0，花费为0
queue <int> q;//寻找最短边的过程类似广度优先遍历，要使用队列
q.push(s);
while(!q.empty())
{
int p=q.front();//设弹出的点为标号为p
q.pop();
for(int i=1;i<=n;i++)//在for循环过程中保留下来的是点i到起点的最短距离和最少花费
{
if(dist[p]+Map[p][i]<dist[i]||(dist[p]+Map[p][i]==dist[i]&&cost[i]>cost[p]+costMap[p][i]))
{
dist[i]=Map[p][i]+dist[p];
cost[i]=costMap[p][i]+cost[p];
q.push(i);
}
}
}
cout<<dist[t]<<" "<<cost[t]<<endl;
}
return 0;
}

最后

以上就是想人陪乌冬面为你收集整理的最短路径问题 （Dijkstra算法）HDU - 3790ProblemInputOutputSample InputSample Output的全部内容，希望文章能够帮你解决最短路径问题 （Dijkstra算法）HDU - 3790ProblemInputOutputSample InputSample Output所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。