K短路

发表于 | 分类于
字数统计: 575 | 阅读时长 ≈ 3

其实短路是有有理有据的做法的，但我不会啊

建立一个以为关键字的优先队列
放入，然后进行扩展
易证，当被第次取出时，为到的短路

考虑用启发式优化来提高效率
到的估计距离可以为到的最短路
对于点，
优先队列以为关键字

还可以继续优化

  • 当取出其中某个点次后，不需要将其再放入优先队列中
  • 对于有距离要求的短路，当取出元素的大于给定值可直接退出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=5050,INF=1<<30;
struct edge{int to;double val;};
struct node{int id;double d;};
int n,m,ans=0,inq[N],cnt[N];
double E,f[N];
vector<edge> e[N],r[N];
queue<int> Q;
struct cmp
{
    bool operator()(node a,node b)
    {
        return a.d+f[a.id]>b.d+f[b.id];
    }
};
priority_queue<node,vector<node>,cmp> S;
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') {t=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*t;
}
void SPFA(int s)
{
    for(int i=1;i<=n;i++) f[i]=INF;
    f[s]=0,inq[s]=1,Q.push(s);
    while (!Q.empty())
    {
        int x=Q.front();
        Q.pop(),inq[x]=0;
        for(int i=0;i<r[x].size();i++)
        {
            int to=r[x][i].to;
            double val=r[x][i].val;
            if (f[x]+val<f[to])
            {
                f[to]=f[x]+val;
                if (!inq[to]) inq[to]=1,Q.push(to);
            }
        }
    }
}
void A_star(int s,int t,int sz)
{
    S.push((node){s,0});
    while (!S.empty())
    {
        node x=S.top();
        if (cnt[x.id]>sz) return;
        S.pop(),cnt[x.id]++;
        if (x.d>E) return;
        if (x.id==t) 
        {
            ans++,E-=x.d;
            sz=E/x.d;
            memset(cnt,0,sizeof(cnt));
        }
        for(int i=0;i<e[x.id].size();i++)
        {
            int to=e[x.id][i].to;
            double val=e[x.id][i].val;
            if (x.d+val<=E) S.push((node){to,x.d+val});
        }
    }
}
int main()
{
    n=read(),m=read();
    scanf("%lf",&E);
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        double val;
        scanf("%lf",&val);
        e[u].push_back((edge){v,val});
        r[v].push_back((edge){u,val});
    }
    SPFA(n);
    A_star(1,n,E/f[1]); 
    printf("%d\n",ans);
    return 0;
}