题目

题目

做法

目前看下来貌似我的做法的复杂度是比较优秀，是$O(n^3)$

当然，$n=101$，首先，点的个数最多是边的个数加一，这个很好理解。

我们开始思考，走这么多边，肯定是要走环的，对吧，那么有一个假想，如果他就是在一条最短路上的最小边反复横跳呢？

我们用“表面否的算法”（Bellman - Ford算法）处理起点和终点到达各个点在走过$k$条边时的最短路，当然$k$最大为多少呢？，我们假定这条路径就在这里反复横跳，不存在其余的环，那么$k$最大就为点的个数，但是，其实是有可能存在其他环的，因为我们这样来回弹跳，只会造成偶数环，那么如果刚好找个奇数环走一遍，然后改变所需要的边数能让答案更小呢，所以$k$要是最大点数的两倍。当然，至于两个环或者一个偶数环的存在，你都可以把环去掉改成左右横跳，权值更小，但是由于我们很难知道这个边是不是路径上最小的边，所以我们需要假定他是，然后枚举所有的边就行了。

#include<cstdio>
#include<cstring>
#define  N  110
#define  NN  1100
#define  M  210
using  namespace  std;
template<class  T>
inline  T  mymin(T  x,T  y){return  x<y?x:y;}
class  EDGE
{
    public:
        struct  node
        {
            int  y,c,next;
        }a[M];int  len,last[NN];
        void  ins(int  x,int  y,int  c)
        {
            len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;
        }
}a1,a2;
struct  FUCKKK
{
    int  x,y,c;
}fuck[N];
int  f1[M][N],f2[M][N];int  n,m,st,ed;bool  v[N];
int  be[NN],cnt,sta[N];
void  dfs(int  x)
{
    for(int  k=a1.last[x];k;k=a1.a[k].next)
    {
        int  y=a1.a[k].y;
        if(!be[y])
        {
            be[y]=++cnt;sta[cnt]=y;
            dfs(y);
        }
        a2.ins(be[x],be[y],a1.a[k].c);
    }
}
int  main()
{
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    for(int  i=1;i<=m;i++)
    {
        int  c,x,y;scanf("%d%d%d",&c,&x,&y);
        a1.ins(x,y,c);a1.ins(y,x,c);
        fuck[i].x=x;fuck[i].y=y;fuck[i].c=c;
    }
    sta[cnt=1]=st;be[st]=1;
    dfs(st);
    //处理和st,ed相通的点的个数
    memset(f1,30,sizeof(f1));
    memset(f2,30,sizeof(f2));
    f1[0][1]=f2[0][be[ed]]=0;
    int  limit=a2.len;
    for(int  i=0;i<limit;i++)
    {
        for(int  j=1;j<=cnt;j++)
        {
            for(int  k=a2.last[j];k;k=a2.a[k].next)
            {
                int  y=a2.a[k].y;
                f1[i+1][y]=mymin(f1[i+1][y],f1[i][j]+a2.a[k].c);
                f2[i+1][y]=mymin(f2[i+1][y],f2[i][j]+a2.a[k].c);
            }
        }
    }
    //Bellman - Ford
    int  ans=999999999;
    for(int  i=1;i<=m;i++)
    {
        if(!be[fuck[i].x])continue;
        int  x=be[fuck[i].x],y=be[fuck[i].y];
        int  ed1=mymin(limit,n);
        for(int  j=0;j<=ed1;j++)
        {
            int  ed2=mymin(limit,n-j);
            for(int  k=0;k<=ed2;k++)
            {
                if((n-j-k)&1)
                {
                    int  shit=(int)(n-j-k)*fuck[i].c;
                    ans=mymin(mymin(f1[j][x]+f2[k][y],f1[j][y]+f2[k][x])+shit,ans);
                }
                else
                {
                    int  shit=(int)(n-j-k)*fuck[i].c;
                    ans=mymin(mymin(f1[j][x]+f2[k][x],f1[j][y]+f2[k][y])+shit,ans);
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

当然，常数稍稍大了点，但是无所谓啦。

最后的最后，安利一下自己的博客QMQ： https://blog.csdn.net/zhangjianjunab

如果不给安利我会撤下来的