权重网站建设,seo和sem的区别是什么,wordpress营销型大气,视频服务器题意
给出一个图#xff0c;图中的边表示从点u到点v路径上的噪音。给出q个查询#xff0c;问从u到v所经路径上的最小噪音
思路
在使用floyd计算点对之间的路径时#xff0c; D u , v k m i n { D u , v k − 1 , m a x { D u , k k − 1 , D k , v k − 1 } } D_{u, v}^…题意
给出一个图图中的边表示从点u到点v路径上的噪音。给出q个查询问从u到v所经路径上的最小噪音
思路
在使用floyd计算点对之间的路径时 D u , v k m i n { D u , v k − 1 , m a x { D u , k k − 1 , D k , v k − 1 } } D_{u, v}^k min \{D_{u, v}^{k - 1}, max\{D_{u, k}^{k- 1}, D_{k, v}^{k - 1}\}\} Du,vkmin{Du,vk−1,max{Du,kk−1,Dk,vk−1}} 代码如下
#include bits/stdc.husing namespace std;#define _for(i, a, b) for(int i (a); i (b); i)
#define _rep(i, a, b) for (int i (a); i (b); i)const int N 104;
const int INF 1e9;int graph[N][N];void fastio()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
}int main()
{fastio();#ifndef ONLINE_JUDGEifstream fin(f:\\OJ\\uva_in.txt);streambuf* back cin.rdbuf(fin.rdbuf());#endifint kase 1;int c, s, q;while (cin c s q) {if (c 0 s 0 q 0) {break;}if (kase 1) {cout endl;}cout Case # kase endl;_for(i, 0, c) {_for (j, 0, c) {graph[i][j] (i j) ? 0 : INF;}}_for(i, 0, s) {int c1, c2, d;cin c1 c2 d;--c1;--c2;graph[c1][c2] min(graph[c1][c2], d);graph[c2][c1] graph[c1][c2];}_for(k, 0, c) {_for(i, 0, c) {_for(j, 0, c) {if (graph[i][k] ! INF graph[k][j] ! INF) {graph[i][j] min(graph[i][j], max(graph[i][k], graph[k][j]));}}}}_for(i, 0, q) {int c1, c2;cin c1 c2;--c1;--c2;int ans graph[c1][c2];if (ans INF) {cout no path endl;} else {cout ans endl;}}}#ifndef ONLINE_JUDGEcin.rdbuf(back);#endifreturn 0;
}
