[ABC191E] 题解
Tang_poetry_syndrome
·
·
题解
[ABC191E] Come Back Quickly
洛谷题面 Atcoder 题面
题目大意
### 思路
优化 Dijkstra 求最小环的板子。
先来介绍一下堆优化 Dijkstra：
首先定义 $dis_i$ 为原点到点 $i$ 的最短距离。然后按 Dijkstra 跑最短路，不同之处在于用一个大根堆维护邻接最小距离，并以最小距离进行松弛。
这题可以将原点的最小距离也设置成无穷大，在松弛时更新最小值，如果原点的最小距离为无穷大，则输出 `-1`，否则输出原点的最小距离。
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,j,k) for(register int i=j;i<=k;i++)
#define pb push_back
int n,m,a,b,c;
const ll INF=LONG_LONG_MAX;
int main() {
cin>>n>>m;
vector<vector<pair<ll,int> > >g(n);
f(i,1,m)cin>>a>>b>>c,g[a-1].push_back(make_pair(c,b-1));
f(i,0,n-1){
vector<ll>d(n,INF);
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >q;
q.push(make_pair(0LL,i));
while(!q.empty()){
ll c;
int b;
tie(c,b)=q.top();
q.pop();
if(c>d[b])continue;
ll e=d[b];
if(b==i)e=0;
for(pair<ll,int> p:g[b]) {
ll w=p.first;
int u=p.second;
if(e+w<d[u]) {
d[u]=e+w;
q.push(make_pair(d[u],u));
}
}
}
ll ans=d[i];
if(ans==INF)ans=-1;
cout<<ans<<endl;
}
}
```
[提交记录](https://atcoder.jp/contests/abc191/submissions/46752212)