洛谷 P1186 【玛丽卡】

这道题题目真的想吐槽一下...是在机房同学的解释下才看懂的。就是让你求在可以删一条边的情况下，并且删后保证可以到达终点时，求删了后的最大的最短路径。

70分暴力思路：

枚举删边，然后跑一下最短路即可，思路很简单，下面给出70分代码：

#include <bits/stdc++.h>

using namespace std;

vector<pair<int , int> > e[1010];

int n , m , ans;

int dis[1010] , vis[1010] , l[500010] , r[500010];

void work(int uu , int vv){

	memset(dis , 127 , sizeof(dis));

	memset(vis , 0 , sizeof(vis));

	queue<int> q;

	dis[1] = 0;

	vis[1] = 1;

	q.push(1);

	while(!q.empty()){

		int x = q.front();

		q.pop();

		vis[x] = 0;

		for(int i = 0; i < e[x].size(); i++){

			int y = e[x][i].first , w = e[x][i].second;

			if((x == uu && y == vv) || (x == vv && y == uu)) continue;	//不走这一条路

			if(dis[y] > dis[x] + w){

				dis[y] = dis[x] + w;

				if(!vis[y]){

					vis[y] = 1;

					q.push(y);

				}

			}

		}

	}

	ans = max(ans , dis[n]);

}

int main(){

	cin >> n >> m;

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

		int x , y , z;

		cin >> x >> y >> z;

		l[i] = x , r[i] = y;	//存储每一条边

		e[x].push_back(make_pair(y , z));

		e[y].push_back(make_pair(x , z));

	}

	for(int i = 1; i <= m; i++) work(l[i] , r[i]);	//删除

	cout << ans;

	return 0;

}

100分满分思路：

我们先预处理求一遍最短路，当我们开始删边时，如果删的不是最短路径上的边时，那么答案还是原来的最短路，因为我们最短路要用的边一条没变。所以，我们只需要枚举删掉最短路上的边即可，这样答案一定改变，同时注意能达到终点。下面给出满分代码：

#include <bits/stdc++.h>

using namespace std;

vector<pair<int , int> > e[1010];

int n , m , ans;

int dis[1010] , vis[1010] , pre[1010];

void work(int uu , int vv){

	for(int i = 1; i <= n; i++) vis[i] = 0 , dis[i] = 0x3ffffff;

	queue<int> q;

	dis[1] = 0;

	vis[1] = 1;

	q.push(1);

	while(!q.empty()){

		int x = q.front();

		q.pop();

		vis[x] = 0;

		for(int i = 0; i < e[x].size(); i++){

			int y = e[x][i].first , w = e[x][i].second;

			if((x == uu && y == vv) || (x == vv && y == uu)) continue;

			if(dis[y] > dis[x] + w){

				dis[y] = dis[x] + w;

				if(!vis[y]){

					vis[y] = 1;

					q.push(y);

				}

			}

		}

	}

	ans = max(ans , dis[n]);

}

void p_work(){

	for(int i = 1; i <= n; i++) vis[i] = 0 , dis[i] = 0x3ffffff;

	queue<int> q;

	dis[1] = 0;

	vis[1] = 1;

	q.push(1);

	while(!q.empty()){

		int x = q.front();

		q.pop();

		vis[x] = 0;

		for(int i = 0; i < e[x].size(); i++){

			int y = e[x][i].first , w = e[x][i].second;

			if(dis[y] > dis[x] + w){

				dis[y] = dis[x] + w;

				pre[y] = x;	//记录前驱

				if(!vis[y]){

					vis[y] = 1;

					q.push(y);

				}

			}

		}

	}

	ans = max(ans , dis[n]);

}

int main(){

	scanf("%d%d" , &n , &m);

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

		int x , y , z;

		scanf("%d%d%d" , &x , &y , &z);

		e[x].push_back(make_pair(y , z));

		e[y].push_back(make_pair(x , z));

	}

	p_work();	//预处理删哪些边

	for(int i = n; i; i = pre[i]) work(i , pre[i]);

	cout << ans;

	return 0;

}

巴特西

洛谷 P1186 【玛丽卡】

70分暴力思路：

100分满分思路：

最新文章

热门文章