zoj 2792 poj 2472 106 miles to Chicago

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

题意：最短路径的变种。

思路：任意最短路径算法均可解之，将权值累加求最小值修改为权值累乘求最大值即可。

代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>using namespace std;const int inf = 10000000;
const int maxn = 105;struct node{int v;double w;node(int _v, double _w){v = _v;w = _w;}
};int n,m;
vector<node> list[maxn];
double dist[maxn];
bool inq[maxn];bool input(){cin>>n;if(n == 0) return false;cin>>m;	for(int i = 1; i <= n; i++) list[i].clear();int u,v;int w;for(int i = 0; i < m; i++){cin>>u>>v>>w;list[u].push_back(node(v,w/100.0));list[v].push_back(node(u,w/100.0));}return true;
}void spfa(){queue<int> q;for(int i = 1; i <= n; i++){dist[i] = -inf; inq[i] = false;}dist[1] = 1;q.push(1);inq[1] = true;while(!q.empty()){int u = q.front(); q.pop(); inq[u] = false;for(int i = 0; i < list[u].size(); i++){int v = list[u][i].v;double w = list[u][i].w;if(dist[u] * w > dist[v]){dist[v] = dist[u] * w;if(!inq[v]){q.push(v); inq[v] = true;}}}}}void solve(){spfa();printf("%.6lf percent\n",dist[n]*100.0);
} int main(){while(input()){solve();}return 0;
}

这篇关于zoj 2792 poj 2472 106 miles to Chicago的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---