题目描述

自己点击题目链接

样例

同上

算法1

(*A) $O(我不知道)$

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005],c[100005];
struct oppo{
    int to,s,next;
}rood[100005];
int head[1005],tot;
void add(int from,int to,int s)
{
    rood[++tot].to=to;
    rood[tot].s=s;
    rood[tot].next=head[from];
    head[from]=tot;
}
int n,m;
int s,t,k;
int vis[1005];
bool flag1[1005];
bool flag2[1005];
void djsk()
{
    memset(vis,10,sizeof(vis));
    vis[t]=0;
    flag1[t]=1;
    for(int i=1;i<=n;i++)
    {
        int k=0;
        for(int j=1;j<=n;j++)
            if(flag1[j]&&!flag2[j]&&vis[j]<vis[k])
                k=j;
        flag2[k]=1;
        for(int i=head[k];i;i=rood[i].next)
        {
            flag1[rood[i].to]=1;
            vis[rood[i].to]=min(vis[rood[i].to],vis[k]+rood[i].s);
        }
    }
}
struct vivo{
    int x,s;
    bool operator<(const vivo y)const{  return s+vis[x]>y.s+vis[y.x];   }
}st;
priority_queue< vivo > v;
int ttt;
void bfs()
{
    if(s==t)
        k++;
    int ans=0;
    st.x=s;
    st.s=0;
    v.push(st);
    while(v.size())
    {
        vivo lxl=v.top();
        v.pop();
        if(lxl.x==t)
        {
            ans++;
            if(ans==k)
            {
                cout<<lxl.s<<endl;
                return;
            }
        }
        if(ans==k)
        {
            cout<<lxl.s+vis[lxl.x];
            return;
        }
        for(int i=head[lxl.x];i;i=rood[i].next)
        {
            st.x=rood[i].to;
            st.s=rood[i].s+lxl.s;
            v.push(st);
        }
    }
    cout<<"-1";
    return;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&a[i],&b[i],&c[i]);
        add(b[i],a[i],c[i]);//反向建图 
    }
    cin>>s>>t>>k;
    djsk();
    memset(head,0,sizeof(head));
    tot=0;
    for(int i=1;i<=m;i++)
        add(a[i],b[i],c[i]);//正向建图 
    bfs();
    return 0;
}