题意:

思路:单源最短路问题,Dijkstra算法搞定就可以了,因为要找出最便宜的最短路,所以需要在更新最短距离的时候加一个条件(即当最短距离相等的时候,如果该路径的花费更小,就更新最小花费)就可以了。之前自己学的最短路的水平也就仅限于模板题的水平,现在可以在条件上稍微加一些变化,做了数据结构的作业,顺便加深了自己对最短路(Dijkstra)算法的理解。

题目所给样例的示意图(数据放在了代码的后边):

代码: 

 #include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
#define FRE() freopen("in.txt","r",stdin) using namespace std;
typedef long long ll;
typedef pair<int,int> P;//first是距离,second是点的编号
const int maxn = ;
struct Edge{
int to,c,d;
Edge(int t,int cost,int dis):to(t),c(cost),d(dis){}
};
vector<Edge> G[maxn];
priority_queue<P, vector<P>, greater<P> > que;
int dist[maxn],cost[maxn];
int n,m,st,en; void init(){
int s,e,d,c;
scanf("%d%d%d%d",&n,&m,&st,&en);
for(int i = ; i<m; i++){
scanf("%d%d%d%d",&s,&e,&d,&c);
G[s].push_back(Edge(e,c,d));
G[e].push_back(Edge(s,c,d));
}
for(int i = ; i<n; i++){
dist[i] = INF;
cost[i] = INF;
}
} int main(){
//FRE();
init();
dist[st] = ;
cost[st] = ;
que.push(P(,st));//指的是当前点的最短距离
while(que.size()){
P p = que.top();
que.pop();
int v = p.second;//当前的点
if(p.first > dist[v])continue;
//cout<<"v: "<<v;
for(int i = ; i<G[v].size(); i++){
Edge e = G[v][i];//当最短距离相等的时候而花费更小的时候,更新最短距离的花费
if((dist[e.to] > dist[v]+e.d)||(dist[e.to] == dist[v]+e.d && cost[e.to] > cost[v]+e.c)){
dist[e.to] = dist[v]+e.d;
cost[e.to] = cost[v]+e.c;
//cout<<" cost: "<<cost[e.to];
que.push(P(dist[e.to], e.to));
}
//cout<<" "<<dist[e.to];
}
//cout<<endl;
}
printf("%d %d\n",dist[en],cost[en]);
return ;
}
/*
样例输入:
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
*/

最新文章

  1. ICSharpCode.SharpZipLib 压缩、解压文件 附源码
  2. s3c2440液晶屏驱动 (非内核自带) linux-4.1.24
  3. RegExp对象
  4. uC/OS-II应用程序exe
  5. 项目:DoubleFaceCamera
  6. 用wireshark抓包分析TCP三次握手、四次挥手以及TCP实现可靠传输的机制
  7. Oracle定时执行存储过程
  8. Android,visibility属性
  9. Power-BI费用分析
  10. Java中如何在另一个类里面使用运行类中的对象,举例说明了一下。
  11. 火狐firefox提示“内容编码错误 无法显示您尝试查看的页面,因为它使用了无效或者不支持的压缩格式。”
  12. Contest20140906 ProblemA dp+线段树优化
  13. iOS-OC-基础-NSDictionary常用方法
  14. C++ Primer 学习笔记_33_STL实践与分析(7) --容器适配器
  15. poj3417 Network 树形Dp+LCA
  16. A项目轶事之加入项目2个月
  17. hdfs一直处于safemode模式
  18. docker容器配置nginx负载均衡 -----加权
  19. git 提交的步骤
  20. Linux下搭建redis服务器

热门文章

  1. Cocos2d-x v3.0正式版尝鲜体验【2】 Android平台移植
  2. [JSOI 2012] 玄武密码
  3. 如何通过DirectInput技术针对莱仕达雷驰V3II游戏方向盘编程
  4. 谈谈windows下克隆的坑
  5. php微信开放平台--第三方网页微信扫码登录(OAuth2.0)
  6. Java中的自定义注解
  7. Coursera公开课-Machine_learing:编程作业
  8. B-Tree 漫谈 (从二叉树到二叉搜索树到平衡树到红黑树到B树到B+树到B*树)
  9. 【LeetCode】-- 73. Set Matrix Zeroes
  10. 警告视图及操作表单在xcode7.0中的使用