floyd解法
今天初看dijkstra,先拿这两题练手,其他变形题还是不是很懂。
模版题,纯练打字。。。
HDU 1874:
#include <cstdio>
#define MAXN 200
#define INF 0xfffff
int n;
int Edge[MAXN][MAXN];
int s[MAXN];
int dist[MAXN];
int path[MAXN];
void Dijkstra(int v0) {
int i, j, k;
for (i = 0; i < n; i++) {
dist[i] = Edge[v0][i];
s[i] = 0;
if (i != v0 && INF > dist[i])
path[i] = v0;
else
path[i] = -1;
}
s[v0] = 1;
dist[v0] = 0;
for (i = 0; i < n - 1; i++) {
int min = INF, u = v0;
for (j = 0; j < n; j++)
if (!s[j] && dist[j] < min){
u = j;
min = dist[j];
}//if
s[u] = 1;
for (k = 0; k < n; k++) {
if (!s[k] && Edge[u][k] < INF && dist[u] + Edge[u] [k] < dist[k]) {
dist[k] = dist[u] + Edge[u][k];
path[k] = u;
}//if
}//for
}//for
}
int main() {
int m;
int i, j;
while (scanf("%d%d", &n, &m) != EOF) {
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (i == j)
Edge[i][j] = 0;
else
Edge[i][j] = INF;
int x, y, z;
for (i = 0; i < m; i++) {
scanf("%d%d%d", &x, &y, &z);
if (z < Edge[x][y])
Edge[y][x] = Edge[x][y] = z;
}
scanf("%d%d", &x, &y);
Dijkstra(x);
if (dist[y] < INF)
printf("%d\n", dist[y]);
else
printf("-1\n");
}//while
return 0;
}
HDU 2544:
#include <cstdio>
#define MAXN 200
#define INF 0xfffff
int n;
int Edge[MAXN][MAXN];
int s[MAXN];
int dist[MAXN];
int path[MAXN];
void Dijkstra(int v0) {
int i, j, k;
for (i = 0; i < n; i++) {
dist[i] = Edge[v0][i];
s[i] = 0;
if (i != v0 && INF > dist[i])
path[i] = v0;
else
path[i] = -1;
}
s[v0] = 1;
dist[v0] = 0;
for (i = 0; i < n - 1; i++) {
int min = INF, u = v0;
for (j = 0; j < n; j++)
if (!s[j] && dist[j] < min){
u = j;
min = dist[j];
}//if
s[u] = 1;
for (k = 0; k < n; k++) {
if (!s[k] && Edge[u][k] < INF && dist[u] + Edge[u] [k] < dist[k]) {
dist[k] = dist[u] + Edge[u][k];
path[k] = u;
}//if
}//for
}//for
}
int main() {
int m;
int i, j;
while (scanf("%d%d", &n, &m) && n && m) {
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (i == j)
Edge[i][j] = 0;
else
Edge[i][j] = INF;
int x, y, z;
for (i = 0; i < m; i++) {
scanf("%d%d%d", &x, &y, &z);
if (z < Edge[x-1][y-1])
Edge[y-1][x-1] = Edge[x-1][y-1] = z;
}
Dijkstra(0);
printf("%d\n", dist[n - 1]);
}//while
return 0;
}
分享到:
相关推荐
题目链接题目意思有n个城镇,编号为0~n-1,m条道路,从一个城镇到另一个城镇有多条路,现在问你从一个城镇到另一个城镇的最短距离是多少。其中要注意的是,城镇之间
算法-畅通工程续(HDU-1874)(包含源程序).rar
ACM题库,一些题目和答案,以及解题报告,传上来共享
NULL 博文链接:https://128kj.iteye.com/blog/1716470
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
杭电OnlineJudge 200-2099的解题报告
最短路(HDU-2544).rar
acm hdu as easy as a+b
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
hdu 1695 GCD(欧拉函数+容斥原理).docx
离线OJ题库(HDU ZJU等,部分有答案),需联网。
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
自动探测POJ、HDU、SOJ、ZOJ水题,对于有志于刷遍各种水题的ACMer来说非常有用
HDU最全ac代码
算法-畅通工程(HDU-1232)(包含源程序).rar
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
很好很经典的组合博弈的讲义,HDU 大家下来看看很好
HDU的一题........HDU DP动态规
ACM HDU题目分类,我自己总结的大概只有十来个吧
100道 acm C语言 hdu 解题报告