1378:最短路径(shopth)(信息学奥赛一本通http://ybt.ssoier.cn:8088/problem_show.php?pid=2060)

本文主要是介绍1378:最短路径(shopth)(信息学奥赛一本通http://ybt.ssoier.cn:8088/problem_show.php?pid=2060),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1378:最短路径(shopth)


时间限制: 1000 ms         内存限制: 65536 KB
提交数: 5673     通过数: 2243

【题目描述】

给出一个有向图G=(V, E),和一个源点v0∈V,请写一个程序输出v0和图G中其它顶点的最短路径。只要所有的有向环权值和都是正的,我们就允许图的边有负值。顶点的标号从1到n(n为图G的顶点数)。

【输入】

第1行:一个正数n(2≤n≤80),表示图G的顶点总数。

第2行:一个整数,表示源点v0(v0∈V,v0可以是图G中任意一个顶点)。

第3至第n+2行,用一个邻接矩阵W给出了这个图。

【输出】

共包含n-1行,按照顶点编号从小到大的顺序,每行输出源点v0到一个顶点的最短距离。每行的具体格式参照样例。

【输入样例】

5
1
0 2 - - 10
- 0 3 - 7
- - 0 4 -
- - - 0 5
- - 6 - 0

【输出样例】

(1 -> 2) = 2
(1 -> 3) = 5
(1 -> 4) = 9
(1 -> 5) = 9

【提示】

样例所对应的图如下:


#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <iomanip>
using namespace std;
int next[105][105];
int n ;
int g[105][105];
void init()
{for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){if(i==j)g[i][j]=g[j][i]=0;elseg[i][j]=g[j][i]=1e9;}}
}
void printpath()
{int st=1,ed=n;while(st!=ed){cout<<st<<" ";st=next[st][ed];}printf("%d",ed);
}int s;
void floyd()
{for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){next[i][j]=j;}}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(g[i][j]>g[i][k]+g[k][j]){g[i][j]=g[i][k]+g[k][j];next[i][j]=next[i][k];}}}}for(int i=1;i<=n;i++){if(s!=i){printf("(%d -> %d) = %d\n",s,i,g[s][i]);}}}
int main( )
{cin>>n;   // init();
cin>>s;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){int a;if(scanf("%d",&a)==1)g[i][j]=a;else g[i][j]=99999;}floyd();return 0;
}

 

这篇关于1378:最短路径(shopth)(信息学奥赛一本通http://ybt.ssoier.cn:8088/problem_show.php?pid=2060)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/208149

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码

【Linux】应用层http协议

一、HTTP协议 1.1 简要介绍一下HTTP        我们在网络的应用层中可以自己定义协议,但是,已经有大佬定义了一些现成的,非常好用的应用层协议,供我们直接使用,HTTP(超文本传输协议)就是其中之一。        在互联网世界中,HTTP(超文本传输协议)是一个至关重要的协议,他定义了客户端(如浏览器)与服务器之间如何进行通信,以交换或者传输超文本(比如HTML文档)。

如何确定 Go 语言中 HTTP 连接池的最佳参数?

确定 Go 语言中 HTTP 连接池的最佳参数可以通过以下几种方式: 一、分析应用场景和需求 并发请求量: 确定应用程序在特定时间段内可能同时发起的 HTTP 请求数量。如果并发请求量很高,需要设置较大的连接池参数以满足需求。例如,对于一个高并发的 Web 服务,可能同时有数百个请求在处理,此时需要较大的连接池大小。可以通过压力测试工具模拟高并发场景,观察系统在不同并发请求下的性能表现,从而

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop

Android Environment 获取的路径问题

1. 以获取 /System 路径为例 /*** Return root of the "system" partition holding the core Android OS.* Always present and mounted read-only.*/public static @NonNull File getRootDirectory() {return DIR_ANDR

Anaconda 中遇到CondaHTTPError: HTTP 404 NOT FOUND for url的问题及解决办法

最近在跑一个开源项目遇到了以下问题,查了很多资料都大(抄)同(来)小(抄)异(去)的,解决不了根本问题,费了很大的劲终于得以解决,记录如下: 1、问题及过程: (myenv) D:\Workspace\python\XXXXX>conda install python=3.6.13 Solving environment: done.....Proceed ([y]/n)? yDownloa