题目

Dijsktra基础题,只是多了一个花费,稍稍变动处理就好

#define  _CRT_SECURE_NO_WARNINGS

#include<string.h>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std; const int MAXN=; #define typec int
const typec INF=0x3f3f3f3f;//防止后面溢出,这个不能太大
bool vis[MAXN];
typec cost[MAXN][MAXN],huafei[MAXN][MAXN];
typec lowcost[MAXN],qihuafei[MAXN];
void Dijkstra(int n,int beg)
{
for(int i=;i<=n;i++)
{
lowcost[i]=cost[beg][i];qihuafei[i]=huafei[beg][i];vis[i]=false;
}
for(int i=;i<=n;i++)
{
typec temp=INF;
int k=-;
for(int j=;j<=n;j++)
{
if(!vis[j]&&lowcost[j]<temp)
{
temp=lowcost[j];
k=j;
}
}
vis[k]=true;
for(int l=;l<=n;l++)
{
if(!vis[l])
{
if(lowcost[l]>lowcost[k]+cost[k][l])
{
lowcost[l]=lowcost[k]+cost[k][l];
qihuafei[l]=qihuafei[k]+huafei[k][l];
}
if(lowcost[l]==lowcost[k]+cost[k][l])
{
qihuafei[l]=min(qihuafei[l],qihuafei[k]+huafei[k][l]);
}
}
}
}
} int main()
{
int n,m,i,j,s,t,a,b,c,d;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==&&m==)break;
for(i=;i<=n;i++)
for(j=;j<=n;j++)
huafei[i][j]=cost[i][j]=(i==j)? :INF; for(i=;i<m;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
if(cost[a][b]>c)
{
cost[a][b]=cost[b][a]=c;
huafei[a][b]=huafei[b][a]=d;
}
}
scanf("%d%d",&s,&t);
Dijkstra(n,s);
printf("%d %d\n",lowcost[t],qihuafei[t]);
} return ;
}

最新文章

  1. Java对象序列化剖析
  2. python学习笔记(1)
  3. C++关于文件的读写(续)
  4. Java——标签组件:JLabel
  5. Linux关于vm虚拟机复制后无法启动网卡
  6. Arduino101学习笔记(十)&mdash;&mdash; 串口通信
  7. iOS开发——项目实战总结&amp;数据持久化分析
  8. win32 treeview
  9. Repeater的ItemCreated和ItemDataBind的区别
  10. 智传播客hadoop视频学习笔记(共2天)
  11. docker——Dockerfile创建镜像
  12. 用Python最原始的函数模拟eval函数的浮点数运算功能(2)
  13. Session与Cookie(自定义Session)
  14. PAT DFS,BFS,Dijkstra 题号
  15. 各种软件的安装教程centos mysql tomcat nginx jenkins jira 等等
  16. centos系统swap设置 查看swap分区的方法
  17. Mysql 之 MERGE 存储引擎
  18. session 超时设置
  19. mysql replace()用法
  20. Effective C++ Item 34 区分接口继承与实现继承

热门文章

  1. Java线程角度的内存模型和volatile型变量
  2. &lt;postfix邮件服务下mysql的升级&gt;
  3. c++11: less的用法
  4. 把url后面的.html去掉
  5. mysql主从复制-linux版本
  6. 通信协议之HTTP,UDP,TCP协议
  7. DTCMS列表页自定义参数。
  8. Bundle、Intent、SharedPreferences
  9. Java注意的地方
  10. CSS的IE6、IE7、FF兼容性写法