/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=1598
Name : 1598 find the most comfortable road
Date : Monday, January 23, 2012
Time Stage : 2.5 hours
Result:
5287995 2012-01-23 16:23:56 Accepted 1598
265MS 220K 1916 B
C++ pyy
Test Data :
Review :
枚举+并查集。
这题放在最短路的专题里,最短路实在不会,只好百度一下了。
牛人解题报告:
http://www.cnblogs.com/mrlai/archive/2011/03/31/2001405.html
http://blog.csdn.net/zxddavy/article/details/6612324
//----------------------------------------------------------------------------*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std ;
#define INF (-1)
#define MAXN 1002
typedef __int64 LL ;
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
#define MEM(a, v) memset (a, v, sizeof (a))
struct SARS {
int s, e, c ;
bool operator< (const SARS &s)
{
return c < s.c ;
}
};
bool used[MAXN] ;
int n, m, q ;
int set[MAXN] ;
SARS map[MAXN] ;
int find (int x)
{
while (set[x] != x)
x = set[x] ;
return x ;
}
int main ()
{
int i, j ;
int x, y, c ;
int res ;
while (~scanf ("%d%d", &n, &m))
{
MEM (map, INF) ;
for (i = 0 ; i < m ; ++i)
{
scanf ("%d%d%d", &map[i].s, &map[i].e , &map[i].c) ;
}
sort (map, map+m) ;
scanf ("%d", &q) ;
while (q--)
{
scanf ("%d%d", &x, &y) ;
res = INF ;
for (i = m-1 ; i >= 0 ; --i)
{
for (j = 0 ; j < m ; ++j)
set[j] = j ;
for (j = i ; j >= 0 ; --j)
{
int xx = find (map[j].s) ;
int yy = find (map[j].e) ;
if (xx != yy)
set[xx] = set[yy] ;
if (find (x) == find (y))
{
if (res == INF || res > map[i].c - map[j].c)
{
res = map[i].c - map[j].c ;
}
break ;
}
}
}
printf ("%d\n", res) ;
}
}
return 0 ;
}
</algorithm></queue></string></iostream></cmath></cstdlib></cstring></cstdio>
分享到:
相关推荐
杭州电子科技大学ACM培训课件 来自杭电ACM官方论坛 拿来和大家分享一下 想到有些朋友论坛积分不够 现在特地拿来免费供大家下载 希望对ACM初学者能够有所帮助
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
计算机网络复习大纲_杭电hdu.pdf
计算机网络复习大纲_杭电hdu借鉴.pdf
计算机网络复习大纲_杭电hdu整理.pdf
计算机网络复习大纲_杭电hdu参考.pdf
杭电ACM1005题源代码,AC了的程序,无问题……
杭电ACMhdu1163
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
杭电hdu acm资料所用杭电的acm题
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
HDU2000至2099题的题目以及AC代码(含思路) 适合刚刚接触ACM的同学哦~ emmmm凑字
杭电acm培训课件 杭电acm培训课件 杭电acm培训课件 杭电acm培训课件
包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...
hdu杭电网络编程结课报告 聊天室