陕西住房城乡建设网站百度网站认证

[P6464 传智杯 #2 决赛] 传送门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

问题描述：增加一个传送门，求最小的任意点对间距离和最小值。

思路：

​ n很小，100左右。又要求各个点对之间的距离，dijkstra、spfa不行，优选floyd。暴力floyd，O(n ** 5)，超时。

​ 对于增加了一个传送门而言，传送门相连的两个边上的最小路要进行更新。因此，可以O(n ** 2)遍历传送门的两个点，用两个O(n ** 2)对传送门对应的点中的路径进行更新。

            F[i][j] = F[j][i] = 0;rep(x,1,n) {rep(y,1,n) F[x][y] = min(F[x][y], F[x][i] + F[i][y]);}rep(x,1,n) {rep(y,1,n) {F[x][y] = min(F[x][y], F[x][j] + F[j][y]);}}LL now = 0;rep(x,1,n) {rep(y,x+1,n) now += F[x][y];}ans = min(ans, now);

代码：

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <random>
#include <sstream>
#include <numeric>
#include <stdio.h>
#include <functional>
#include <bitset>
#include <algorithm>
using namespace std;// #define Multiple_groups_of_examples
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false);
#define dbgnb(a) std::cout << #a << " = " << a << '\n';
#define dbgtt cout<<" !!!test!!! "<<endl;
#define rep(i,x,n) for(int i = x; i <= n; i++)#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs secondtypedef long long LL;
typedef pair<int,int> PII;const int INF = 0x3f3f3f3f;
const int N = 1e2 + 21;
int f[N][N], F[N][N];void inpfile();
void solve() {int n,m; cin>>n>>m;rep(i,1,n) {rep(j,1,n) {if(i == j) f[i][j] = 0;else f[i][j] = INF;}}rep(i,1,m) {int u,v,a; cin>>u>>v>>a;f[u][v] = f[v][u] = min(a, f[u][v]);}rep(k,1,n) {rep(i,1,n) {rep(j,1,n) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);}}// rep(i,1,n) cout<<f[i][n]<<endl;LL ans = INF;rep(i,1,n) {rep(j,i+1,n) {if(i == j) continue;memcpy(F, f, sizeof(F));// rep(x,1,n) {//     rep(y,1,n) F[x][y] = f[x][y];// }F[i][j] = F[j][i] = 0;rep(x,1,n) {rep(y,1,n) F[x][y] = min(F[x][y], F[x][i] + F[i][y]);}rep(x,1,n) {rep(y,1,n) {F[x][y] = min(F[x][y], F[x][j] + F[j][y]);}}LL now = 0;rep(x,1,n) {rep(y,x+1,n) now += F[x][y];}ans = min(ans, now);}}cout<<ans;
}
int main()
{#ifdef Multiple_groups_of_examplesint T; cin>>T;while(T--)#endifsolve();return 0;
}
void inpfile() {#define mytest#ifdef mytestfreopen("ANSWER.txt", "w",stdout);#endif
}