旅游规划 (Dijkstra)
输入
输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。
输出
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。
输入样例
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
输出样例
3 40
代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long int INF=0x3f3f3f3f; //定义无穷大
const int maxn=600; //n的最大值为500
typedef pair<int,int> P;//first是距离,second是点的编号
//边结点，含边的终点，路费，距离
struct edge{int to,cost,dis;edge(int t,int c,int d):to(t),cost(c),dis(d){}
};
vector<edge> G[maxn]; //点与点之间的边矩阵
priority_queue<P,vector<P>,greater<P> > que;//已经规划好的部分
int dis[maxn],cost[maxn];//目前最优路程，目前最优花费
int n,m,start,direct; //第一行参数输入 int main(){cin>>n>>m>>start>>direct;int s,d,len,cost;int i=0;while(i<m){ //输入每一条边的信息 cin>>s>>d>>len>>cost;G[s].push_back(edge(d,cost,len)); //无向图，边是双向可达的 G[d].push_back(edge(s,cost,len));i++;}//初始化路程和费用为无穷大 for(i=0;i<n;i++){dis[i]=INF;cost[i]=INF;}dis[start]=0; cost[start]=0; //起点到自己为0 que.push(P(0,start));//起点到当前节点的最短距离while(que.size()){ //队列不为空时 P p=que.top(); //取出已规划好的点中最新的点 que.pop();int v=p.second; //取该点的编号 if(p.first>dis[v]) continue; //起点到该点的距离与当前最优距离作比较 for(int i=0;i<G[v].size();i++){ //遍历点v的各条边 edge e=G[v][i];if(dis[e.to]>dis[v]+e.dis||dis[e.to]==dis[v]+e.dis&&cost[e.to]>cost[v]+e.cost){//若点v上一步到该边终点的最优路程大于经过点v得到的最优路程//或路程距离相等，比较花费 dis[e.to]=dis[v]+e.dis;cost[e.to]=cost[v]+e.cost;que.push(P(dis[e.to],e.to));}} } cout<<dis[direct]<<" "<<cost[direct]<<endl;return 0;
}
本文链接：https://my.lmcjl.com/post/6606.html
展开阅读全文
4 评论