地铁修建

201703-4

这题就是最短路的一种变形，不是求两点之间的最短路，而是求所有路径中的最长边的最小值。
这里还是使用d数组，但是定义不同了，这里的d[i]就是表示从起点到i的路径中最长边中的最小值。
在松弛的时候，注意是d[i]>max(d[u],cost),max保证了是所有路径中的最长边，>号保证了是最小值。
这里使用前向星+优先队列对dijikstra算法进行了优化。

//#include <iostream>

//#include<cstdio>

//#include<algorithm>

//#include<cstring>

#include<bits/stdc++.h>

using namespace std;

const int maxn=100005;

const int maxm=200005;

const int INF=0X3F3F3F3F;

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int n,m;

int e;

struct node{

	int dis;

	int to;

	bool operator<(const node& t)const{

		return dis>t.dis;

	}

};

struct edge{

	int to;

	int cost;

	int next;

};

edge edges[2*maxm];

int head[maxn];

int d[maxn];//d[i]表示起点到i的所有路径中最大边的最小值

void dijikstra(int s){

	priority_queue<node>q;

	q.push(node{0,s});

	memset(d,INF,sizeof(d));

	d[s]=0;

	while(!q.empty()){

		node temp=q.top();

		q.pop();

		int u=temp.to;

		int dis=temp.dis;

		if(d[u]<dis){

			continue;

		}

		for(int i=head[u];i!=-1;i=edges[i].next) {

			edge ed=edges[i];

			if(d[ed.to]>max(d[u],ed.cost)){

				d[ed.to]=max(d[u],ed.cost);

				q.push(node{d[ed.to],ed.to});

			}

		}

	}

}

int main() {

	ios::sync_with_stdio(false);

	cin.tie(0);

	cin>>n>>m;

	memset(head,-1,sizeof(head));

	for(int i=0;i<m;i++){

		int a,b,c;

		cin>>a>>b>>c;

		edges[e].to=b;

		edges[e].cost=c;

		edges[e].next=head[a];

		head[a]=e++;

		edges[e].to=a;

		edges[e].cost=c;

		edges[e].next=head[b];

		head[b]=e++;

	}

	dijikstra(1);

	cout<<d[n]<<endl;

	return 0;

}

巴特西

CCF(地铁修建)：向前星+dijikstra+求a到b所有路径中最长边中的最小值

地铁修建

201703-4

最新文章

热门文章