题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=1874
畅通工程续
Description
某省自从实行了很多年的畅通工程计划后,终于修建了很多路。不过路多了也不好,每次要从一个城镇到另一个城镇时,都有许多种道路方案可以选择,而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在,已知起点和终点,请你计算出要从起点到终点,最短需要行走多少距离
Input
本题目包含多组数据,请处理到文件结束。
每组数据第一行包含两个正整数$N$和$M\ (0<N<200,0<M<1000)$,分别代表现有城镇的数目和已修建的道路的数目。城镇分别以$0~N-1$编号。
接下来是$M$行道路信息。每一行有三个整数$A,B,X\ (0 \leq A,B<N,A \neq B,0<X<10000)$,表示城镇$A$和城镇$B$之间有一条长度为$X$的双向道路。
再接下一行有两个整数$S,T\ (0 \leq S,T<N)$,分别代表起点和终点。
Output
对于每组数据,请在一行里输出最短需要行走的距离。如果不存在从$S$到$T$的路线,就输出-1.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1
单源最短路。。
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using std::cin;
using std::cout;
using std::endl;
using std::find;
using std::sort;
using std::pair;
using std::vector;
using std::multimap;
using std::priority_queue;
#define pb(e) push_back(e)
#define sz(c) (int)(c).size()
#define mp(a, b) make_pair(a, b)
#define all(c) (c).begin(), (c).end()
#define iter(c) decltype((c).begin())
#define cls(arr,val) memset(arr,val,sizeof(arr))
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
const int N = ;
struct P {
int w, v;
P(int i = , int j = ) :w(i), v(j) {}
inline bool operator<(const P &a) const {
return w > a.w;
}
};
struct Node { int to, w, next; };
struct Dijkstra {
Node G[N];
int tot, u, v, w, dist[N], head[N];
inline void init() {
tot = ;
cls(head, -), cls(dist, 0x3f);
}
inline void add_edge(int u, int v, int w) {
G[tot] = { v, w, head[u] }; head[u] = tot++;
}
inline void built(int m) {
rep(i, m) {
scanf("%d %d %d", &u, &v, &w);
add_edge(u, v, w), add_edge(v, u, w);
}
scanf("%d %d", &u, &v);
}
inline void dijkstra() {
dist[u] = ;
priority_queue<P> q;
q.push(P(, u));
while (!q.empty()) {
P t = q.top(); q.pop();
int x = t.v;
if (dist[x] < t.w) continue;
for (int i = head[x]; ~i; i = G[i].next) {
int &d = dist[G[i].to];
if (d > dist[x] + G[i].w) {
d = dist[x] + G[i].w;
q.push(P(d, G[i].to));
}
}
}
printf("%d\n", dist[v] == (int)0x3f3f3f3f ? - : dist[v]);
}
}go;
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif
int n, m;
while (~scanf("%d %d", &n, &m)) {
go.init();
go.built(m);
go.dijkstra();
}
return ;
}
hdu 1874 畅通工程续的更多相关文章
-
ACM: HDU 1874 畅通工程续-Dijkstra算法
HDU 1874 畅通工程续 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Desc ...
-
HDU 1874 畅通工程续-- Dijkstra算法详解 单源点最短路问题
参考 此题Dijkstra算法,一次AC.这个算法时间复杂度O(n2)附上该算法的演示图(来自*): 附上: 迪科斯彻算法分解(优酷) problem link -> HDU 1874 ...
-
HDU 1874畅通工程续(迪杰斯特拉算法)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1874 畅通工程续 Time Limit: 3000/1000 MS (Java/Others) ...
-
hdu 1874 畅通工程续 Dijkstra
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1874 题目分析:输入起点和终点,顶点的个数,已连通的边. 输出起点到终点的最短路径,若不存在,输出-1 ...
-
HDU 1874 畅通工程续【Floyd算法实现】
畅通工程续 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submi ...
-
hdu 1874 畅通工程续(求最短距离,dijkstra,floyd)
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1874 /************************************************* ...
-
HDU 1874 畅通工程续(最短路/spfa Dijkstra 邻接矩阵+邻接表)
题目链接: 传送门 畅通工程续 Time Limit: 1000MS Memory Limit: 65536K Description 某省自从实行了很多年的畅通工程计划后,终于修建了很多路. ...
-
hdu 1874 畅通工程续(迪杰斯特拉优先队列,floyd,spfa)
畅通工程续 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Subm ...
-
HDU——1874畅通工程续(Dijkstra与SPFA)
畅通工程续 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submiss ...
随机推荐
-
java泛型基础
泛型是Java SE 1.5的新特性, 泛型的本质是参数化类型, 也就是说所操作的数据类型被指定为一个参数. 这种参数类型可以用在类.接口和方法的创建中, 分别称为泛型类.泛型接口.泛型方法. Ja ...
-
Linux安装FTP服务
转自:http://blog.csdn.net/huangbiao86/article/details/6641952 ftp服务器 1. 在Linux和其他机器之间共享文件(在linux下安装ft ...
-
Java --ClassLoader创建、加载class、卸载class
一.java提供了三种ClassLoader对Class进行加载: 1.BootStrap ClassLoader:称为启动类加载器,是Java类加载层次中最顶层的类加载器,负责加载JDK中的核心类库 ...
-
Caffe学习系列(5):其它常用层及参数
本文讲解一些其它的常用层,包括:softmax_loss层,Inner Product层,accuracy层,reshape层和dropout层及其它们的参数配置. 1.softmax-loss so ...
-
Eclipse Gtk+
From: http://hi.baidu.com/spmno/item/9425018707f295dfd1f8cdbe 1. Project->Properties,然后选 C/C++ Bu ...
-
【笔记】ASP.NET MVC Model元数据
问题1:什么叫Model元数据? Model元数据,是针对数据类型的一种描述信息.由于复杂类型(或者说类型嵌套的存在,比如CustomerModel中有一个属性为复杂类型Address)的存在,因此M ...
-
APP中数据加载的6种方式-b
我们看到的APP,往往有着华丽的启动界面,然后就是漫长的数据加载等待,甚至在无网络的时候,整个处于不可用状态.那么我们怎么处理好界面交互中的加载设计,保证体验无缝衔接,保证用户没有漫长的等待感,而可以 ...
-
【转贴】gdb中的信号(signal)相关调试技巧
一篇不错的帖子,讲的是gdb中的信号(signal)相关调试技巧 转自Magic C++论坛 http://www.magicunix.com/index_ch.html http://www.m ...
-
jQuery实现置顶和置底特效
原文地址:http://www.jqueryba.com/3403.html <script src="jquery.min.js" type="text/java ...
-
Ceph的Block分析
一个块是一个连续的字节序列(例如一个512字节的连续数据是一个块).基于块的存储接口通常是旋转介质,例如磁盘.光盘.软盘等.块设备接口的普及使得可以用虚拟的块设备成为和大容量数据存储系统交互的接口,如 ...