luoguP1186 玛丽卡

最近看了看最短路树,于是就来做这道题了qwq(我才不会告诉你是因为看了这道题才去看的最短路树)

$所谓最短路树,就是在跑dijktra的时候随手记录个小东西,然后形成一个树,这棵树的根节点\left(也就是最短路起点\right)到每个节点的距离就是源点到该点的最短路$所谓最短路树,就是在跑dijktra的时候随手记录个小东西,然后形成一个树,这棵树的根节点(也就是最短路起点)到每个节点的距离就是源点到该点的最短路

$然后最短路树有一个神奇的性质:就是只要不破坏树上的n-1条边,源点到各点的最短路就不会变$然后最短路树有一个神奇的性质:就是只要不破坏树上的n−1条边,源点到各点的最短路就不会变

$然后,这道题的做法就是选择要删除的边,然后再跑最短路,并与之前的比较$然后,这道题的做法就是选择要删除的边,然后再跑最短路,并与之前的比较

$然后,我们有最短路树之后,我们就不用枚举每条边了,只需要尝试删除最短路树上的边就行了$然后,我们有最短路树之后,我们就不用枚举每条边了,只需要尝试删除最短路树上的边就行了

$\left(反正删掉别的地方的边也不会影响最短路qwq\right)$(反正删掉别的地方的边也不会影响最短路qwq)

$现在,唯一的问题就是怎么来建立最短路树了qwq$现在,唯一的问题就是怎么来建立最短路树了qwq

$首先,我们要额外维护几个数组,pre\left[i\right]代表i号节点最短路前面连的边,data\left[i\right]代表i号节点最短路前面的点$首先,我们要额外维护几个数组,pre[i]代表i号节点最短路前面连的边,data[i]代表i号节点最短路前面的点

$然后....就没有然后了$然后....就没有然后了

$现在就是上代码了$现在就是上代码了

$然后唯一的技巧就是.....$然后唯一的技巧就是.....

            if(dis[v] > dis[u] + a[i].z ) { // 转移最短路的时候,顺手记录一下qwq
            	data[v] = u ;
            	pre[v] = i ; 
                dis[v] = dis[u] + a[i].z ;
                q.push(make_pair(dis[v],v)) ;
            }

$下面真的放代码了qwq$下面真的放代码了qwq

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#define maxn 2100000 
#pragma GCC optimize(5)
using namespace std ;
int data[maxn] , pre[maxn] ;
struct dy{
	int x , y , z , next ;
}a[maxn] ;
int head[maxn] , vis[maxn] , dis[maxn] , t ;
int read() {
	int x = 0 , f = 1 ; char s = getchar() ;
	while(s > '9' || s < '0') {if(s == '-') f = -1 ; s = getchar() ;}
	while(s <='9' && s >='0') {x = x * 10 + (s-'0'); s = getchar() ;}
	return x*f ;
}
void add(int x ,int y ,int z) {
	a[++t].x = x ;
	a[t].y = y ;
	a[t].z = z ;
	a[t].next = head[x] ;
	head[x] = t ;
}
typedef pair<int,int>pa ;
void dijkstra(int s) {
    memset(dis,0x3f,sizeof(dis)) ;
    memset(vis,0,sizeof(vis)) ;
    priority_queue<pa,vector<pa>,greater<pa> >q ;
    dis[s] = 0 , vis[s] = 0 ;
    q.push(make_pair(dis[s],s)) ;
    while(!q.empty()) {
        int u = q.top().second ;
        q.pop() ;
        if(vis[u]) continue ;
        vis[u] = 1 ;
        for(int i = head[u] ; i ; i = a[i].next ) {
            int v = a[i].y ;
            if(dis[v] > dis[u] + a[i].z ) {
            	data[v] = u ;
            	pre[v] = i ; 
                dis[v] = dis[u] + a[i].z ;
                q.push(make_pair(dis[v],v)) ;
            }
        }
    }
} 
int n , m ;
int Vis[maxn] ;
int main () {
	n = read() , m = read() ;
	for(int i = 1 ; i <= m ; i ++) {
		int x = read () , y = read() , z = read() ;
		add(x,y,z) ;
		add(y,x,z) ;
	}
	dijkstra(1) ;
	int num = 0 ;
	for(int i = n ; i ; i = data[i]) { 
		 Vis[++num] = pre[i] ;
 	}
	int ans = dis[n] ;
	for(int i = 1 ; i <= num ; i ++ ) {
		int v = Vis[i] ;
		int res = a[v].z ;
		a[v].z = 999999999 ;
		dijkstra(1) ;
		a[v].z = res ;
		ans = max(ans,dis[n]) ;
	}
	cout << ans <<endl ;
	return 0 ;
} 

$完结散花!$完结散花!