九度OJ 1341:艾薇儿的演唱会 (最短路)
2024-10-17 22:25:23
时间限制:1 秒
内存限制:32 兆
特殊判题:否
提交:528
解决:241
- 题目描述:
-
艾薇儿今天来到了中国,她计划两天后在哈尔滨举行一场个人的演唱会。由于出现了紧急情况,演唱会的举办方要求艾薇儿提前举行演唱会。艾薇儿现在在北京,她需要找出一条从北京到哈尔滨耗时最短的线路,以便尽快到达哈尔滨。
中国的铁路线非常复杂,有很多条路线可以从北京到达哈尔滨。艾薇儿在网上找到了铁路线各个线路上所需花费的时间,但是她还是看不出来哪一条线路可以最快地到达哈尔滨。你有办法帮助艾薇儿找出从北京到哈尔滨所需的最短时间吗?找出来的人可以免费获得现场演唱会门票一张哦。
- 输入:
-
输入的第一行包括一个整数N(2<=N<=100),代表艾薇儿手上拿到的设有铁路站点的城市的个数,其中城市从1到n进行编号。以及M(1<=M<=1000),代表有M条铁路线路,每条铁路线路只连接两个城市。
接下来的一行有两个数,a和b(1<=a,b<=N),分别表示北京和哈尔滨的编号。
接下来有M行,每行有三个数x,y(1<=x,y<=N),t(1<=t<=1000),表示从城市x到城市y所需时间为t。
- 输出:
-
请输出艾薇儿从北京到哈尔滨最少需要多长时间。你可以放心地认为肯定存在一条路线可以从北京到哈尔滨。
- 样例输入:
-
3 4
1 3
1 2 1
3 2 3
2 3 4
3 1 8
- 样例输出:
-
4
- 提示:
-
1.火车能从城市x到城市y,就能从城市y到城市x,并且同一列火车来回所花费的时间是一样的。如果在x和y之间有不止一辆火车通行,则不同火车从x到y或者从y到x所花费的时间可能不相同。
2.虽然城市数有N个,但不保证所有的城市都能互相到达。可以保证的是,从北京到哈尔滨一定会有一条通路。
思路:
最短路问题,需要注意重边的更新。
代码:
#include <stdio.h>
#include <limits.h> #define N 100
#define M 10000
#define INF (INT_MAX/2) int n;
int v[N];
int d[N];
int p[N][N]; void init()
{
int i, j;
for (i=0; i<n; i++)
{
v[i] = 0;
d[i] = INF;
for (j=0; j<n; j++)
p[i][j] = INF;
}
} void printDij()
{
for (int i=0; i<n; i++)
printf("%d ", d[i]);
printf("\n");
} void dij(int k, int r)
{
int i;
v[k] = 1;
d[k] = 0;
while(k != r)
{
for (i=0; i<n; i++)
{
if (!v[i] && p[i][k] + d[k] < d[i])
d[i] = p[i][k] + d[k];
}
int md = INF;
for (i=0; i<n; i++)
{
if (!v[i] && d[i] < md)
{
k = i;
md = d[i];
}
}
if (d[k] == INF)
break;
v[k] = 1;
}
} int main()
{
int i, m, x, y, a, b, t;
while(scanf("%d%d", &n, &m) != EOF)
{
if (n == 0 && m == 0)
break;
init();
scanf("%d%d", &x, &y);
for (i=0; i<m; i++)
{
scanf("%d%d%d", &a, &b, &t);
if (t < p[a-1][b-1])
p[a-1][b-1] = p[b-1][a-1] = t;
}
dij(x-1, y-1);
printf("%d\n", d[y-1]);
}
return 0;
}
/**************************************************************
Problem: 1341
User: liangrx06
Language: C
Result: Accepted
Time:60 ms
Memory:952 kb
****************************************************************/
最新文章
- AC日记——蓬莱山辉夜 codevs 2830
- SAP模板
- Mysql查询重复记录
- [转]jquery开发自定义的插件总结
- sass学习笔记1
- Server ran out of threads to serve requests. Consider raising the ThreadsPerChild setting
- 5、面向对象以及winform的简单运用(方法重载、隐藏、重写与虚方法)
- 如何在 Ubuntu 14.04 里面配置 chroot 环境
- SecureCRT设置
- CentOS搭建VSFTP
- Apache与php的整合(经典版),花了一天去配置成功经验
- Clash of Clans(COC)资源压缩解密
- 使用iptraf,ifstat查看网络流量
- Java Object中的equals和hashCode
- 网络安全之在Kali Linux上安装Openvas
- flask完成文件上传功能
- Python类之类的成员
- 【java】异常
- Python学习【01】编程语言简介,Python安装及环境变量配置
- JMeter执行压测输出HTML图形化报表(二)