火炬传递 题解

· · 个人记录

公约

  1. E.u,E.v,E.w

题目

\color{#7F1083}\text{BSOJ} 和 \color{#3498DB} \text{Luogu}

火炬传递

题目描述

### 输入格式 输入第一行包含两个整数 $n$，$m$，表示岛屿个数和桥的个数。 接下来$m$行，第 $i$ 行两个整数，$x$，$y$, $c$，表示可以从岛 $x$ 经过第 $i$ 座桥到达岛 $y$，花费为 $c$。 ### 输出格式 输出一行，最小花费。 ### 样例 #1 #### 样例输入 #1 ``` 10 15 8 9 1 6 2 10 2 4 5 3 1 5 1 4 3 6 7 10 2 9 9 1 5 8 10 6 5 3 10 4 8 6 8 6 5 4 6 4 8 3 2 9 7 8 5 ``` #### 样例输出 #1 ``` 13 ``` ### 提示 对于 $50\%$ 的数据 $n\le200, m\le2000

对于100\%的数据 n\le1000, m\le10000

思路

由暴力到正解

我们撕开一个环，发现：一个环就是一条边加上一条更长的边。

所以我们思考：

对于每一条边 E ，其实形成边权和最小的环便是E.u <- E.v 的最短路径加上 E.w 的结果。

求答案：O(m) 。

那怎么快速全源最短路呢？

以每个点为源点分别跑一次 Dijkstra 。

总时间复杂度：O(n^2\log n)。

下面是 \mathbf{Coding} 和 \mathbf{Typing} (\mathbf{copying})时间！

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3+10;
const int MAXM = 1e4+10;
const int INF = 0x3f3f3f3f;
//Grath
int n,m,x,y,z,ans = INF;
struct edge{
    int to,w;
};
vector<edge> v[MAXN];
//Dijkstra
int dis[MAXN][MAXN];
bool vis[MAXN][MAXN];
bool operator < (const edge &b,const edge &a){
    return a.w<b.w;
}
priority_queue<edge> pq;
void dijkstra(int s){
    dis[s][s] = 0;
    pq.push({s,0});
    while(!pq.empty()){
        auto x = pq.top();
        pq.pop();
        if(vis[s][x.to]) continue;
        vis[s][x.to] = true;
        for(auto i:v[x.to]){
            if(dis[s][i.to]>dis[s][x.to]+i.w){
                dis[s][i.to] = dis[s][x.to]+i.w;
                pq.push({i.to,dis[s][i.to]});
            }
        }
    }
}
signed main(){
    memset(dis,0x3f,sizeof(dis));
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back({y,z});
    }
    for(int i = 1;i<=n;i++) dijkstra(i);
    for(int i = 1;i<=n;i++){
        for(auto j:v[i]){
            ans = min(ans,j.w+dis[j.to][i]);
        }
    }
    printf("%d",ans);
    return 0;
}