1
已解决
高级守护
0
已采纳
中级启示者
Floyd不香吗
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(g[i][j]>g[i][k]+g[k][j])
g[i][j]=g[i][k]+g[k][j];//Floyd
int maxn=-INF;
for(int i=1;i<=n;i++)
if(g[1][i]>maxn)
maxn=g[1][i];
if(maxn==INF)
cout<<-1;
else
cout<<maxn;
0
高级守护
d
0
高级守护
突然知道了，理解错题意了……已AC，所以怎么删帖？
谁随便回复一个我就采纳Ta！
0
被禁言
资深天翼
额
0
资深守护
采纳我呗
0
高级光能
我来随便回复你一个，望采纳！谢谢！！！
0
中级天翼
望采纳，谢谢
0
修练者
望采纳，谢谢谢
0
新手启示者
0
中级天翼
望采纳，谢谢
0
缔造者
大佬nb啊
0
被禁言
新手守护
真牛逼class！！！
0
高级天翼
望采纳，谢谢
0
中级守护
0
中级守护
0
初级天翼
从书上看的，望采纳
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 105,M = 405;
int d[N],n,m;
int idx,h[N],e[M],ne[M],w[M];
priority_queue<PII> pq;
bool st[N];
void add(int a,int b,int c){
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int miao(){
memset(d,0x3f,sizeof d);
memset(st,false,0);
d[1] = 0;
pq.push({-d[1],1});
int ans = 0;
while(pq.size()){
int t = pq.top().second;
ans = max(ans,d[t]);
pq.pop();
if(st[t]) continue;
st[t] = true;
for(int i = h[t];~i;i = ne[i]){
int j = e[i];
if(!st[j] && d[t] + w[i] < d[j]){
d[j] = d[t] + w[i];
pq.push({-d[j],j});
}
}
}
for(int i = 1;i <= n;i++){
if(d[i] == 0x3f3f3f3f){
ans = -1;
break;
}
}
return ans;
}
int main(){
cin>>n>>m;
int a,b,c;
memset(h,-1,sizeof h);
for(int i = 0;i < m;i++){
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
cout<<miao()<<endl;
return 0;
}
