当前位置:网站首页>ZOJ1298(单源最短路径)
ZOJ1298(单源最短路径)
2022-08-09 11:09:00 【AlanLiu6】
这道题因为循环判断语句WA了三十多发,生活完全无法自理.
卒
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 100000100 //无穷大
#define MAXN 550 //顶点个数的最大值
int n,m; //顶点个数
int Edge[MAXN][MAXN]; //邻接矩阵
int S[MAXN]; //Dijkstra算法用到的三个数组
int dist[MAXN];
int caseno = 1;
void Dijkstra(int v0)
{
int i,j;
for(i = 1;i <= n;i++){
dist[i] = Edge[v0][i];
S[i] = 0;
}
S[v0] = 1; //顶点v0加入到顶点集合S
for(i = 1;i < n;i++){
int min = INF,u;
//选择当前集合T中具有最短路径的顶点u
for(j = 1;j <= n;j++){
if(!S[j]&&dist[j] < min){
u = j; min = dist[j];
}
}
S[u] = 1;
for(j = 1;j <= n;j++){
if(!S[j] && Edge[u][j] != INF&&dist[u]+Edge[u][j] < dist[j]){
dist[j] = dist[u] + Edge[u][j];
}
}
}
double maxtime1 = -INF,maxtime2 = -INF;
int pos,pos1,pos2; //最后倒下的关键时间及位置
for(i = 1;i <= n;i++){
if(dist[i] > maxtime1){
maxtime1 = dist[i]; pos = i;
}
}
//每一行中间普通牌倒下的时间最大值及位置
for(i = 1;i <= n;i++){
for(j = i+1;j <= n;j++){
double t = (dist[i]+dist[j]+Edge[i][j])/2.0;
if(Edge[i][j] < INF&&t > maxtime2){
maxtime2 = t;
pos1 = i;
pos2 = j;
}
}
}
if(maxtime2 > maxtime1)
printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n\n",maxtime2,pos1,pos2);
else printf("The last domino falls after %.1f seconds, at key domino %d.\n\n",maxtime1,pos);
}
int main()
{
while (~scanf("%d%d", &n, &m) && (n||m)) {
memset(Edge,0,sizeof(Edge));
int i,j;//读入顶点个数n,边数
int u,v,w; //边的起点和终点及权值
for(i = 1;i <= m ;i++){
scanf("%d%d%d",&u,&v,&w); //读入边的起点和终点,权值
Edge[u][v] = Edge[v][u] = w; //构造邻接矩阵
}
for(i = 1;i <= n;i++){
for(j = i;j <= n;j++){
if(j == i) Edge[i][j] = 0;
else if(Edge[i][j] == 0)Edge[i][j] = Edge[j][i] = INF;
}
}
printf("System #%d\n",caseno++);
Dijkstra(1); //求顶点0到其他顶点的最短路径
}
return 0;
}
边栏推荐
- People | How did I grow quickly from programmer to architect?
- ICML 2022 | Out-of-Distribution检测与深最近的邻居
- mysql8.0和navicat premium15下载安装
- 1009 Product of Polynomials C语言多项式乘积(25分)
- 1008 Elevator (20分)
- uni-app 自带的picker封装一个日期-时间选择器
- 图片查看器viewer
- 使用.NET简单实现一个Redis的高性能克隆版(四、五)
- 信号量SIGCHLD的使用,如何让父进程得知子进程执行结束,如何让父进程区分多个子进程的结束
- es6对象迭代器iterator
猜你喜欢
MDK添加注释模板
CentOS6.5 32bit安装Oracle、ArcSde、Apache等配置说明
x86 exception handling and interrupt mechanism (2) interrupt vector table
美的数字化平台 iBUILDING 背后的技术选型
Netscope: Online visualization tool for neural network structures
mysql8.0和navicat premium15下载安装
Antdv+Asp.net WebApi开发学生信息管理系统(一)
x86 Exception Handling and Interrupt Mechanism (1) Overview of the source and handling of interrupts
End-to-End Object Detection with Fully Convolutional Network学习笔记
Quartz的理解
随机推荐
SQL Server查询优化
Number theory knowledge
排序--快排(图解)
Numpy常用操作博客合集
【C language】typedef的使用:结构体、基本数据类型、数组
使用gdb调试多进程程序、同时调试父进程和子进程
wpf path xaml写法和c#写法对比
caffe ---make all editing error
MySQL传统方案和通过SSH连接哪个好?
uni-app 自带的picker封装一个日期-时间选择器
数论知识点
PAT 1015 进制转换
程序员的专属浪漫——用3D Engine 5分钟实现烟花绽放效果
b站up主:空狐公子 --矩阵求导(分母布局)课程笔记
ICML 2022 | Out-of-Distribution检测与深最近的邻居
程序员的专属浪漫——用3D Engine 5分钟实现烟花绽放效果
fidder为什么不会抓包的问题
使用.NET简单实现一个Redis的高性能克隆版(四、五)
fork creates multiple child processes
1005 Spell It Right (20分)