zoj 2027 Travelling Fee

本文主要是介绍zoj 2027 Travelling Fee，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：求从起点除法到终点的最少费用，题目比一般的最短路径多了个限制条件，可以免去花费最多的一条边的费用。

思路：用一个数组maxi[i][j]记录从i到j的路径中，一条路最多花费多少，将递推式改成 edge[i][j] = min (edge[i][k] + edge[k][j] - max(maxi[i][k],maxi[k][j]) , edge[i][j] - maxi[i][j])，当起点为s终点为t时，输出edge[s][t] - maxi[s][t]即可。

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>using namespace std;struct node{int v;int w;node(int _v, int _w){v = _v;w = _w;}
};const int inf = 10000000;
const int maxn = 205;int m;
int n;//城市数 
int edge[maxn][maxn];	//
int maxi[maxn][maxn];	// 从i到j路径中的最大费用 
map<string,int>  Map;
string s,t;bool input(){if(!(cin>>s))//如果读取失败 return false;cin>>t;cin>>m;n = 0;Map.clear();for(int i = 0; i < maxn; i++) {for(int j = 0; j < maxn; j++){edge[i][j] = inf;maxi[i][j] = 0;}}string u,v;int w;for(int i = 0; i < m; i++){cin>>u>>v;cin>>w;if(Map[u] == 0) Map[u] = ++n;if(Map[v] == 0) Map[v] = ++n;int tu = Map[u];int tv = Map[v];edge[tu][tv] = w; maxi[tu][tv] = w;edge[tv][tu] = w; maxi[tv][tu] = w;}return true;
}void floyd(){for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){int t = max(maxi[i][k],maxi[k][j]);//最长的一段路 if(edge[i][k] + edge[k][j] - t < edge[i][j] - maxi[i][j]){edge[i][j] = edge[i][k] + edge[k][j];maxi[i][j] = t;	//更换免去费用的路段 }}}}
}void solve(){floyd();cout<<edge[Map[s]][Map[t]] - maxi[Map[s]][Map[t]]<<"\n";
}int main(){while(input()){solve();}return 0;
}

这篇关于zoj 2027 Travelling Fee的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---