codeforces144——D. Missile Silos
原题链接
题意：
给定一个n点m边的无向图，给定起点，求和起点最短距离为l的点有多少个（可以是点也可以在边上）
思路：
首先求一遍最短路，处理出每个点到起点的最短距离，这样遍历一遍点就可以求出和起点最短距离为l的点的个数。
再来考虑该点在边上的情况，我们遍历每条边，如果该点在边上，假设边的顶点为u和v，无非三种情况，一是该点在u和v的中点上，二是该点更加靠近u，三是该点更加靠近v。
接下来将逐一分析。我们假设起点S，边的顶点u，v的关系如下图。
当该点在u，v中点时，一定满足dis[u]+dis[v]+w==2*l; 当该点更靠近u时，首先就是dis[u]<l，说明该点不在s和u的中间；再就是l-dis[u]<w，说明多出来的这部分不会超过v；然后就是w-(l-dis[u])>l-dis[v]，说明该点到u的距离小于该点到v的距离，即该点更靠近u。 当该点更靠近v时也同理。 具体细节如下：
int u
=edge
[j
].u
,v
=edge
[j
].e
,w
=edge
[j
].w
;
if(dis
[u
]<l
&&l
-dis
[u
]<w
&&w
-l
+dis
[u
]>l
-dis
[v
]) res
++;
if(dis
[v
]<l
&&l
-dis
[v
]<w
&&w
-l
+dis
[v
]>l
-dis
[u
]) res
++;
if(dis
[u
]<l
&&dis
[v
]<l
&&dis
[u
]+dis
[v
]+w
==l
*2) res
++;
代码：
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
typedef pair
<ll
,ll
>PLL
;
typedef pair
<int,int>PII
;
typedef pair
<double,double>PDD
;
#define I_int ll
inline ll
read()
{
ll x
=0,f
=1;char ch
=getchar();
while(ch
<'0'||ch
>'9'){if(ch
=='-')f
=-1;ch
=getchar();}
while(ch
>='0'&&ch
<='9'){x
=x
*10+ch
-'0';ch
=getchar();}
return x
*f
;
}
char F
[200];
inline void out(I_int x
) {
if (x
== 0) return (void) (putchar('0'));
I_int tmp
= x
> 0 ? x
: -x
;
if (x
< 0) putchar('-');
int cnt
= 0;
while (tmp
> 0) {
F
[cnt
++] = tmp
% 10 + '0';
tmp
/= 10;
}
while (cnt
> 0) putchar(F
[--cnt
]);
}
ll
ksm(ll a
,ll b
,ll p
){ll res
=1;while(b
){if(b
&1)res
=res
*a
%p
;a
=a
*a
%p
;b
>>=1;}return res
;}
const int inf
=0x3f3f3f3f,mod
=998244353;
const ll INF
= 0x3f3f3f3f3f3f3f3f;
const int maxn
=1e6+7,maxm
=3e5+7,N
=1e6+7;
const double PI
= atan(1.0)*4;
int n
,m
,s
;
struct node
{
int e
,ne
,w
,u
;
}edge
[maxn
];
int h
[maxn
],idx
;
void add(int u
,int v
,int w
){
edge
[idx
].u
=u
,edge
[idx
].e
=v
,edge
[idx
].w
=w
,edge
[idx
].ne
=h
[u
],h
[u
]=idx
++;
}
int dis
[maxn
],st
[maxn
];
void spfa(int s
){
memset(dis
,0x3f,sizeof dis
);
queue
<int>q
;
q
.push(s
);dis
[s
]=0;st
[s
]=1;
while(!q
.empty()){
int t
=q
.front();q
.pop();
st
[t
]=0;
for(int i
=h
[t
];i
!=-1;i
=edge
[i
].ne
){
int j
=edge
[i
].e
;
if(dis
[j
]>dis
[t
]+edge
[i
].w
){
dis
[j
]=dis
[t
]+edge
[i
].w
;
if(!st
[j
]){
q
.push(j
);
st
[j
]=1;
}
}
}
}
}
int main(){
memset(h
,-1,sizeof h
);
n
=read(),m
=read(),s
=read();
for(int i
=1;i
<=m
;i
++){
int u
=read(),v
=read(),w
=read();
add(u
,v
,w
);add(v
,u
,w
);
}
int l
=read();
spfa(s
);
int res
=0;
for(int i
=1;i
<=n
;i
++)
if(dis
[i
]==l
) res
++;
for(int j
=0;j
<idx
;j
+=2){
int u
=edge
[j
].u
,v
=edge
[j
].e
,w
=edge
[j
].w
;
if(dis
[u
]<l
&&l
-dis
[u
]<w
&&w
-l
+dis
[u
]>l
-dis
[v
]) res
++;
if(dis
[v
]<l
&&l
-dis
[v
]<w
&&w
-l
+dis
[v
]>l
-dis
[u
]) res
++;
if(dis
[u
]<l
&&dis
[v
]<l
&&dis
[u
]+dis
[v
]+w
==l
*2) res
++;
}
out(res
);
return 0;
}
