Floyd挂了求助

luqyou @ 2022-10-17 17:01:08

#include<bits/stdc++.h>
using namespace std;
int a,b,f[11][11],n=3;
int main(){
    memset(f,0x3f,sizeof(f));
    scanf("%d%d",&a,&b); 
    f[1][2]=a;
    f[1][1]=0;
    f[2][1]=a;
    f[2][2]=0;
    f[3][2]=b;
    f[2][3]=b;
    f[3][3]=0;
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
        }
    }
    printf("%d",f[1][3]);
    return 0; 
}

by Usada_Pekora @ 2022-10-17 17:20:08

@luqyou

#include<bits/stdc++.h>
using namespace std;
long long a,b,f[11][11],n=3;
int main(){
    scanf("%lld%lld",&a,&b);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            f[i][j] = (i != j) * INT_MAX;
    f[1][2]=a;
    f[2][3]=b;
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
        }
    }
    printf("%lld",f[1][3]);
    return 0; 
}

by a2lyaXNhbWUgbWFyaXNh @ 2022-10-17 17:21:07

借楼一问，有没有什么能处理负环的图论最短路算法？/yiw

by luqyou @ 2022-10-17 17:22:36

@S__B SPFA

by Resolute_Faith @ 2022-10-17 17:30:14

怎么为之处理负环？是判断还是？

by a2lyaXNhbWUgbWFyaXNh @ 2022-10-17 17:36:06

@luqyou SPFA只能负权边不能负环吧？

处理负环指的是求单源最短路

by seanlsy @ 2022-10-17 22:01:27

用 spfa

#include <bits/stdc++.h>
using namespace std;
int n,m,u,v,w,sh[5],vis[5];
bitset<5> bt;
struct edge
{
  int dis,v;
};
vector<edge> g[5];
inline void spfa(int x)
{
  bt[x]=vis[x]=1;
  memset(sh,127,sizeof sh);
  sh[x]=0;
  queue<int> q;
  q.push(x);
  while(q.size())
  {
    u=q.front();
    q.pop();
    bt[u]=0;
    for(int i=0; i<g[u].size(); i++)
    {
      edge y=g[u][i];
      if(sh[y.v]>sh[u]+y.dis)
      {
        sh[y.v]=sh[u]+y.dis;
        if(!bt[y.v])
        {
          q.push(y.v);
          bt[y.v]=1;
        }
      }
    }
  }
}
int main()
{
  cin>>n>>m;
  g[1].push_back({n,2});
  g[2].push_back({m,3});
  spfa(1);
  printf("%d\n",sh[3]);
  return 0;
}

by Zvelig1205 @ 2022-10-23 21:12:50

@luqyou 建有向图不可以吗

by Zvelig1205 @ 2022-10-23 21:13:52

@S__B 都有负环了，哪来的最短路

SPFA 和 floyd 都可以用来判断有无负环

by a2lyaXNhbWUgbWFyaXNh @ 2022-10-24 08:06:37

@Zvelig1205 az

by diqiuyi @ 2022-10-28 17:08:50

不要建双向边