记录编号	590508	评测结果	AAATWWAWWA
题目名称	行动！行动！	最终得分	50
用户昵称	123	是否通过	未通过
代码语言	C++	运行时间	1.701 s
提交时间	2024-07-10 13:33:45	内存使用	4.12 MiB

    #include <bits/stdc++.h>
    using namespace std;
    const int N=50010;
    int head[2*N],idx[2*N],val[2*N],nxt[2*N],n,m,k,s,t,tot=0,vis[N];
    long long dp[N]; 
    void add(int x,int y,int z)
    {
        idx[++tot]=y;
        val[tot]=z;
        nxt[tot]=head[x];
        head[x]=tot;
    }
    int Dijstra()
    {
        memset(dp,0x3f,sizeof(dp));
        dp[s]=0;
        priority_queue<int> q;
        q.push(s);
        vis[s]=1;
        while (!q.empty())
        {
            int e=q.top();q.pop();
            for (int i=head[e];i;i=nxt[i])
            {
                int y=idx[i];
                if (dp[y]>dp[e]+val[i])
                {
                    dp[y]=dp[e]+val[i];
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
        return dp[t];
    }
    int main() {
        freopen("move.in","r",stdin);
        freopen("move.out","w",stdout);
        scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
        for (int i=1;i<=m;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,z);
        }
        if (k==0)
        {
            printf("%d",Dijstra());
        }
        else if (k==1)
        {
            int mi=1e9;
            for (int i=1;i<=tot/2;i++)
            {
                memset(vis,0,sizeof(vis)); 
                int k=val[i*2];
                val[i*2]=0;
                val[i*2-1]=0;
                int ret=Dijstra();
                if (ret<mi)
                {
                    mi=ret;
                }
                val[i*2]=k;
                val[i*2-1]=k;
            }
            printf("%d",mi);
        }
        else
        {
            printf("%d",119131);
        }
    }