首页 > 代码库 > [luoguP1186] 玛丽卡（spfa）

[luoguP1186] 玛丽卡（spfa）

2024-09-19 15:06:35   215人阅读

传送门

 

因为要随机删除一条边，而枚举所有边肯定会超时，经过发现，先求出一遍最短路，而要删除的边肯定在最短路径上，删除其他的边对最短路没有影响。

所以可以先求出最短路，再枚举删除最短路上的每一条边再求最短路。

 

——代码

技术分享
 1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5  6 using namespace std; 7  8 const int MAXN = 1001; 9 int n, m, cnt, ans, qu, qv;10 int head[MAXN], to[MAXN * MAXN], next[MAXN * MAXN], val[MAXN * MAXN], dis[MAXN], pre[MAXN];11 bool vis[MAXN], flag;12 queue <int> q;13 14 inline void add(int x, int y, int z)15 {16     to[cnt] = y;17     val[cnt] = z;18     next[cnt] = head[x];19     head[x] = cnt++;20 }21 22 inline void spfa(int u)23 {24     int i, v;25     while(!q.empty()) q.pop();26     memset(vis, 0, sizeof(vis));27     memset(dis, 127 / 3, sizeof(dis));28     q.push(u);29     dis[u] = 0;30     while(!q.empty())31     {32         u = q.front();33         q.pop();34         vis[u] = 0;35         for(i = head[u]; i != -1; i = next[i])36         {37             v = to[i];38             if((u == qu && v == qv) || (u == qv && v == qu)) continue;39             if(dis[v] > dis[u] + val[i])40             {41                 dis[v] = dis[u] + val[i];42                 if(!flag) pre[v] = u;43                 if(!vis[v])44                 {45                     vis[v] = 1;46                     q.push(v);47                 }48             }49         }50     }51 }52 53 int main()54 {55     int i, x, y, z;56     scanf("%d %d", &n, &m);57     memset(pre, -1, sizeof(pre));58     memset(head, -1, sizeof(head));59     for(i = 1; i <= m; i++)60     {61         scanf("%d %d %d", &x, &y, &z);62         add(x, y, z);63         add(y, x, z);64     }65     spfa(1);66     flag = 1;67     for(i = n; i != -1; i = pre[i])68     {69         qu = i;70         qv = pre[i];71         spfa(1);72         if(dis[n] != 707406378) ans = max(ans, dis[n]);73     }74     printf("%d", ans);75     return 0;76 }
View Code

 

[luoguP1186] 玛丽卡（spfa）


联系
我们