玛丽卡

发表于 更新于 分类于

Problem’s Website

  • 玛丽卡

    Solution

  • 这道题的题意可能不太好懂，大体意思是切掉一张图中的一条边，使从1到n的最短路最长，输出长度。
  • 因为在很多比赛中，SPFA会被卡，保险起见，这道题我们用堆优化的Dijkstra，我们先跑一遍Dij，记录一下路径，然后分别切断，跑Dij，求出最大时间，即为答案，注意一点，这道题我们用链式前向星要多记录一个from,为一条边的出发点，方便切边。

    Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #define gc getchar()
    #define INF 0x7fffffff / 3
    using namespace std;
    int sc() {
    	int xx = 0, ff = 1; char cch = gc;
    	while(cch < '0' || cch > '9') {
    		if(cch == '-') ff = -1; cch = gc;
    	}
    	while(cch >= '0' && cch <= '9') {
    		xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
    	}
    	return xx * ff;
    }
    struct node {
    	int next, to, from, dis;
    }edge[499510 << 1];
    struct heap {
    	int id, num;
    	bool operator < (const heap &x) const {
    		return num > x.num;
    	}
    };
    int n, m, cnt, ans;
    int head[499510], dis[1010], pre[1010];
    bool vis[1010];
    priority_queue <heap> q;
    void ADD(int from, int to, int dis) {
    	edge[++cnt].next = head[from];
    	edge[cnt].from = from;
    	edge[cnt].to = to;
    	edge[cnt].dis = dis;
    	head[from] = cnt;
    }
    void Dijkstra(bool pd) {
    	memset(dis, 0x7f, sizeof(dis));
    	memset(vis, 0, sizeof(vis));
    	while(!q.empty())
    		q.pop();
    	dis[1] = 0;
    	q.push((heap){1, 0});
    	while(!q.empty()) {
    		heap now = q.top(); q.pop();
    		if(vis[now.id]) continue;
    		vis[now.id] = true;
    		for(int i = head[now.id]; i; i = edge[i].next) {
    			int to = edge[i].to;
    			if(dis[to] > dis[now.id] + edge[i].dis) {
    				dis[to] = dis[now.id] + edge[i].dis;
    				if(pd)
    					pre[to] = i;
    				if(!vis[to])
    					q.push((heap){to, dis[to]});
    			}
    		}
    	}
    }
    int main() {
    	n = sc(); m = sc();
    	for(int i = 1; i <= m; i++) {
    		int x = sc(), y = sc(), z = sc();
    		ADD(x, y, z);
    		ADD(y, x, z);
    	}
    	Dijkstra(true);
    	int now = n;
    	while(now != 1) {
    		int la = edge[pre[now]].dis;
    		edge[pre[now]].dis = INF;
    		Dijkstra(false);
    		ans = max(ans, dis[n]);
    		edge[pre[now]].dis = la;
    		now = edge[pre[now]].from;
    	}
    	printf("%d\n", ans);
    	return 0;
    }

rp++