51nod 2650 最短缩减路径

本文主要是介绍51nod 2650 最短缩减路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

原题链接

51nod 2650
题目类型：$2$级题$♦♦$
AC记录：Accepted

题目大意

给出一张包含$n$个节点、$m$条边的无向图，现在你可以任意取仅一条边，将它的边权变成$\lfloor \frac{1}{2}\times 边权\rfloor$，请你求出此时图上两点$s,t$间可能的最短路径长度。

输入格式

第一行两个数$n,m$，分别表示节点数和边数，以空格隔开；
之后$m$行，每行3个数$u,v,w_i$，表示点$u$和$v$间有一条权值为$w_i$的边，
最后一行，两个数$s,t$表示选择的两个点，以空格隔开。

输出格式

输出一个数，表示$s,t$间最短路径的长度。
$\mathbf{S}\mathbf{a}\mathbf{m}\mathbf{p}\mathbf{l}\mathbf{e}$ $\mathbf{I}\mathbf{n}\mathbf{p}\mathbf{u}\mathbf{t}$

4 3
1 2 6
1 3 4
2 4 2
3 4

$\mathbf{S}\mathbf{a}\mathbf{m}\mathbf{p}\mathbf{l}\mathbf{e}$ $\mathbf{O}\mathbf{u}\mathbf{t}\mathbf{p}\mathbf{u}\mathbf{t}$

9

$\mathbf{H}\mathbf{i}\mathbf{n}\mathbf{t}\&\mathbf{E}\mathbf{x}\mathbf{p}\mathbf{l}\mathbf{a}\mathbf{i}\mathbf{n}$
样例所示的图如下图所示。

把连接$1,2$的边变成他的$\frac{1}{2}$，此时总路径最短，是4+3+2=9。

数据范围

对于$100\%$的数据，$其中1\le n\le 500，1\le m\le 50000，1\le 边权\le 500000$，保证所有边权为偶数。

解题思路

这题可以用$Spfa$解决。
很多人看到这一题，立马想到直接找最大的一条边减半，就可以得到最小值，但是并不对，如下面的例子：

3 3
1 2 2
2 3 2
1 3 100
1 3

依照上面的思路，把$100$那条边减半，答案应该为2+2=4。但实际答案却是2+1=3。
那么正确的解法是什么呢？

解法一：
建一个复制图，再把复制图和原图连接起来，样例如下图。
蓝边代表原图，绿边代表复制图，红边代表权值减半的边。

由于建了这个图之后，从蓝图走到绿图的方法只有通过红边，即把权值减半，而绿图又不可能走到蓝图，所以就满足只把一条边减半的要求。
最后对于这个图做一遍$Spfa$就可以了。

解法二：
对于这个图，从起点到终点做一遍$Spfa$，再从终点到起点做一遍$Spfa$，最后枚举中间的一条边，把他减半，再取其中的最大值，即可。

---

最后，祝大家早日

上代码

$$Code1$$

#include<bits/stdc++.h>using namespace std;vector<pair<int,int> >  road[300010];
queue<int>              q;
bool                    vis[300010];
int                     dist[300010];
int                     n,m;int main()
{ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;for(int i=1; i<=m; i++){int x,y,z;cin>>x>>y>>z;road[x+0*n].push_back(make_pair(y+0*n,  z));road[x+0*n].push_back(make_pair(y+1*n,z/2));road[x+1*n].push_back(make_pair(y+1*n,  z));road[y+0*n].push_back(make_pair(x+0*n,  z));road[y+0*n].push_back(make_pair(x+1*n,z/2));road[y+1*n].push_back(make_pair(x+1*n,  z));}memset(dist,0x7f,sizeof(dist));int f,t;cin>>f>>t;if(f==t){cout<<0<<endl;return 0;}dist[f]=0;vis[f]=true;q.push(f);while(q.size()){int now=q.front();q.pop();vis[now]=false;for(int i=0; i<road[now].size(); i++){int id=road[now][i].first;int val=road[now][i].second;if(dist[now]+val<dist[id]){dist[id]=dist[now]+val;if(!vis[id]){q.push(id);vis[id]=true;}}}}// for(int i=1; i<=2*n; i++)//     cout<<dist[i]<<" ";// cout<<endl;cout<<dist[t+n]<<endl;return 0;
}

$$Code2$$

#include<bits/stdc++.h>using namespace std;vector<pair<int,int> >  road[510];
int                     dist[3][510];
int                     n,m,f,t;void spfa(int f,int pos)
{queue<int> q;bool vis[510];memset(dist[pos],0x7f,sizeof(dist[pos]));memset(vis,false,sizeof(vis));dist[pos][f]=0;vis[f]=true;q.push(f);while(q.size()){int now=q.front();q.pop();vis[now]=false;for(int i=0; i<road[now].size(); i++){int id=road[now][i].first;int val=road[now][i].second;if(dist[pos][now]+val<dist[pos][id]){dist[pos][id]=dist[pos][now]+val;if(!vis[id]){q.push(id);vis[id]=true;}}}}return;
}int main()
{cin>>n>>m;for(int i=1; i<=m; i++){int x,y,z;cin>>x>>y>>z;road[x].push_back(make_pair(y,z));road[y].push_back(make_pair(x,z));}cin>>f>>t;if(f==t){cout<<0<<endl;return 0;}spfa(f,1);spfa(t,2);int tar=2147483647;for(int i=1; i<=n; i++)for(int j=0; j<road[i].size(); j++)tar=min(tar,dist[1][i]+dist[2][road[i][j].first]+road[i][j].second/2);// for(int i=1; i<=2; i++)// {//     for(int j=1; j<=n; j++)//         cout<<dist[i][j]<<" ";//     cout<<endl;// }cout<<tar<<endl;return 0;
}

完美切题$\sim$

这篇关于51nod 2650 最短缩减路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---