3713796_ac_188ms_1044k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#define maxv 1001
#define INF 2100000000

using namespace std;

int n, e, l;

set <int> s;

struct node
{
	int value;
	int tar;
 
	bool operator<(const node & x) const
	{
		if (value > x.value) return true;
		return false;
	}
};

priority_queue< node ,vector<node> > q;
vector <node> edge[maxv];
int maxlen;

int mindis()
{
	int dis[maxv];
	bool used[maxv];
	int i, j, k;

	while (!q.empty()) q.pop();
 
	for (i = 0; i < n; ++i) 
	{
		dis[i]=INF;
	}
	memset(used,false,sizeof(used));
 
	node temp,temp2;
	temp.value=0;
	temp.tar=0;
	q.push(temp);
 
	while (!q.empty())
	{
		while (!q.empty() && used[q.top().tar]) q.pop();
		if (q.empty()) break;
		temp=q.top();
		q.pop();

		used[temp.tar]=true;
		dis[temp.tar]=temp.value;

		for (k=0;k<edge[temp.tar].size();++k) 
		{
			j=edge[temp.tar][k].tar;
			if (dis[temp.tar]+(edge[temp.tar][k].value>maxlen)< dis[j] && !used[j])
			{
				dis[j]=dis[temp.tar]+(edge[temp.tar][k].value>maxlen);
				temp2.tar=j;
				temp2.value=dis[j];
				q.push(temp2);
			}
		}
	}
	return dis[n - 1];
}

bool check(int len)
{
	maxlen = len;
	return mindis() <= l;
}

void solve()
{
	int min, mid, max;
	vector <int> len;

	for (set <int> ::iterator i = s.begin(); i != s.end(); ++i)
	{
		len.push_back((*i));
	}
	min = 0;
	max = len.size();
	int ans = -1;
	while (min < max)
	{
		mid = (min + max) >> 1;
		if (check(len.at(mid)))
		{
			ans = len.at(mid);
			max = mid;
		}
		else
			min = mid + 1;
	}
	if (ans == len.at(0))
		ans = 0;
	printf("%d\n", ans);
}

void input()
{
	int i, j, k, w;
 
	scanf("%d%d%d",&n, &e, &l);
	for (i = 0; i < e; ++i)
	{
		scanf("%d%d%d", &j, &k, &w);
		node t;
		s.insert(w);
		j--;k--;
		t.tar = k;t.value = w;
		edge[j].push_back(t);
		t.tar = j;
		edge[k].push_back(t);
	}
}

int main()
{
	input();
	solve();
	return 0;
}