九度oj 1545奇怪的连通图

444878909

浏览: 635546 次

最近访客更多访客>>

iams13

songhait

google企鹅

7522453

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1289)

社区版块

存档分类

题目1545：奇怪的连通图

时间限制：1 秒

内存限制：128 兆

特殊判题：否

提交：164

解决：44

题目描述：

已知一个无向带权图，求最小整数k。使仅使用权值小于等于k的边，节点1可以与节点n连通。

输入：

输入包含多组测试用例，每组测试用例的开头为一个整数n(1 <= n <= 10000)，m(1 <= m <= 100000)，代表该带权图的顶点个数，和边的个数。
接下去m行，描述图上边的信息，包括三个整数,a(1 <= a <= n),b(1 <= b <= n),c(1 <= c <= 1000000),表示连接顶点a和顶点b的无向边，其权值为c。

输出：

输出为一个整数k，若找不到一个整数满足条件，则输出-1。

样例输入：

样例输出：

3
5
-1

比赛的时候没想出来。

很笨地用DFS递归枚举。。

然后果断超时。。

一个数据都没过。。

然后第二天早上起来果断用BFS写了一下。。

wa~~

有点小激动，因为没有超时。

然后将队列改为优先队列果断A了

yes！！

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
struct node
{
    int ne;
    int va;
};
struct node1
{
	int next;
	int m;
	bool operator < (const node1& a) const
	{
		return m>a.m;
	}
};
vector<node> map[10002];
int visit[10002];
int n,t,in;
int mmin(int aa,int bb)
{
    return aa<bb?aa:bb;
}
int max(int aa,int bb)
{
    return aa>bb?aa:bb;
}

int BFS()
{
	int xiao = 1000008;
	priority_queue<node1> qu;
	struct node1 needru,needpush,var;
	needru.next = 1;
	needru.m = 0;
	qu.push(needru);
	visit[1] = 1;
	while(!qu.empty())
	{
		needpush = qu.top();
		qu.pop();
		if(needpush.next==n)
			xiao = mmin(xiao,needpush.m);
		int len = map[needpush.next].size();
		visit[needpush.next] = 1;
		for(int i=0;i<len;i++)
		{
			if(!visit[map[needpush.next][i].ne])
			{
				var.next = map[needpush.next][i].ne;
				var.m = max(map[needpush.next][i].va,needpush.m);
				qu.push(var);
				
			}
		}
	}
	return xiao;

}
int main()
{
    int i,j,a,b;
    struct node qq;
    while(scanf("%d%d",&n,&t)!=EOF)
    {
        in = 1000008;
        memset(visit,0,sizeof(visit));
        for(i=0;i<t;i++)
        {
            scanf("%d%d%d",&a,&b,&j);
            qq.ne = b;
            qq.va = j;
            map[a].push_back(qq);
            qq.ne = a;
            map[b].push_back(qq);
        }
        visit[1] = 1;
		in = BFS();
        if(in!=1000008)
        printf("%d\n",in);
        else
            printf("-1\n");
        for(i=0;i<=n;i++)
        map[i].clear();
    }
 
    return 0;
}

分享到：