本文共 1829 字，大约阅读时间需要 6 分钟。
很显然的贪心呀，
#include #include #include #include #include #include #include #include #include #include using namespace std;#define MAX 5100#define MAXL 201000#define INF 1e11#define lim 1e-11inline int read(){ int x=0,t=1;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t;}struct Line{ int v,next;double w;}e[MAXL*2];int h[MAX],cnt=1;inline void Add(int u,int v,double w){ e[cnt]=(Line){v,h[u],w}; h[u]=cnt++;}int N,M;double En;double dis1[MAX];bool vis[MAX];int ans;void SPFA1(){ for(int i=1;i<=N;++i)dis1[i]=INF; dis1[N]=0;vis[N]=true; queue Q;while(!Q.empty())Q.pop(); Q.push(N); while(!Q.empty()) { int u=Q.front();Q.pop(); for(int i=h[u];i;i=e[i].next) { if(i&1)continue; int v=e[i].v; if(dis1[v]>dis1[u]+e[i].w) { dis1[v]=dis1[u]+e[i].w; if(!vis[v]) { vis[v]=true; Q.push(v); } } } vis[u]=false; }}struct Node{ double val; int num;};inline bool operator <(Node a,Node b){ return a.val+dis1[a.num]>b.val+dis1[b.num];}void SPFA(){ priority_queue Q;while(!Q.empty())Q.pop(); Q.push((Node){0.00,1}); while(!Q.empty()) { Node u=Q.top();Q.pop(); if(u.val-En>lim||lim>En)break; if(u.num==N)ans++,En-=u.val; for(int i=h[u.num];i;i=e[i].next) { if((i^1)&1)continue; int v=e[i].v; if(u.val+e[i].w-En>lim)continue; Q.push((Node){u.val+e[i].w,v}); } }}int main(){ N=read();M=read(); scanf("%lf",&En); for(int i=1;i<=M;++i) { int u=read(),v=read();double w; scanf("%lf",&w); Add(u,v,w);Add(v,u,w); } SPFA1(); SPFA(); printf("%d\n",ans); return 0;}
转载于:https://www.cnblogs.com/cjyyb/p/7623761.html