洛谷P1186玛丽卡

传送门啦

先跑一遍最短路，将最短路的路径记录下来，然后枚举每一条最短路的边，将其断掉，记录此时的1-n的时间，取其中最大的一个时间即为所求。

（通过 $ cut[][] $ 和 $ f[] $ 进行操作）

注意这个题是个稠密图，可能会卡 $ spfa $ ，所以我用了堆优化 $ dijk $ 。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int maxn = 1005;

const int maxm = 500005;

inline int read(){char ch = getchar();int f = 1 , x = 0;while(ch > '9' || ch < '0'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}return x * f;}

int n,m,u,v,w;

int head[maxn],tot;

int dis[maxn],f[maxn],ans;

bool flag,cut[maxn][maxn];

struct Edge{

	int from,to,next,val;

}edge[maxm << 1];

struct Node{

	int u,d;

	bool operator < (const Node &f) const {

		return d > f.d;

	}

}	;

void add(int u,int v,int w){

	edge[++tot].from = u;

	edge[tot].to = v;

	edge[tot].val = w;

	edge[tot].next = head[u];

	head[u] = tot;

}

void dijk(int s){

	for(int i=1;i<=n;i++)  dis[i] = 1e9;

	priority_queue<Node> q;

	dis[s] = 0;

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

	while(!q.empty()){

		Node cur = q.top();

		q.pop();

		int u = cur.u , d = cur.d;

		if(d != dis[u]) continue;

		for(int i=head[u];i;i=edge[i].next){

			int v = edge[i].to;

			if(dis[v] > dis[u] + edge[i].val && cut[u][v] == 0){

				if(!flag)  f[v] = u;

				dis[v] = dis[u] + edge[i].val;

				q.push((Node) {v , dis[v]});

			}

		}

	}

}	

int main(){

	n = read(); m = read();

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

		u = read(); v = read(); w = read();

		add(u , v , w);

		add(v , u , w);

	}

	dijk(1);

	flag = 1;

	for(int i=n;i!=1;i=f[i]){

		cut[f[i]][i] = 1;

		cut[i][f[i]] = 1;

		dijk(1);

		cut[f[i]][i] = 0;

		cut[i][f[i]] = 0;

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

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

洛谷P1186玛丽卡

传送门啦

最新文章

热门文章