Useful Edges Codeforces Solution
You are given a weighted undirected graph on nn vertices along with qq triples (u,v,l)(u,v,l), where in each triple uu and vv are vertices and ll is a positive integer. An edge ee is called useful if there is at least one triple (u,v,l)(u,v,l) and a path (not necessarily simple) with the following properties:
Useful Edges solution codeforces
- uu and vv are the endpoints of this path,
- ee is one of the edges of this path,
- the sum of weights of all edges on this path doesn’t exceed ll.
Please print the number of useful edges in this graph.Input Useful Edges solution codeforces
The first line contains two integers nn and mm (2≤n≤6002≤n≤600, 0≤m≤n(n−1)20≤m≤n(n−1)2).
Each of the following mm lines contains three integers uu, vv and ww (1≤u,v≤n1≤u,v≤n, u≠vu≠v, 1≤w≤1091≤w≤109), denoting an edge connecting vertices uu and vv and having a weight ww.
The following line contains the only integer qq (1≤q≤n(n−1)21≤q≤n(n−1)2) denoting the number of triples.
Each of the following qq lines contains three integers uu, vv and ll (1≤u,v≤n1≤u,v≤n, u≠vu≠v, 1≤l≤1091≤l≤109) denoting a triple (u,v,l)(u,v,l).
It’s guaranteed that:
- the graph doesn’t contain loops or multiple edges;
- all pairs (u,v)(u,v) in the triples are also different.
Output Useful Edges solution codeforces
Print a single integer denoting the number of useful edges in the graph.Examplesinput
4 6 1 2 1 2 3 1 3 4 1 1 3 3 2 4 3 1 4 5 1 1 4 4
output Useful Edges solution codeforcesCopy
5
input
4 2 1 2 10 3 4 10 6 1 2 11 1 3 11 1 4 11 2 3 11 2 4 11 3 4 9
output Useful Edges solution codeforces
1
input
3 2 1 2 1 2 3 2 1 1 2 5
output
2
Note Useful Edges solution codeforces
In the first example each edge is useful, except the one of weight 55.
In the second example only edge between 11 and 22 is useful, because it belongs to the path 1−21−2, and 10≤1110≤11. The edge between 33 and 44, on the other hand, is not useful.
In the third example both edges are useful, for there is a path 1−2−3−21−2−3−2 of length exactly 55. Please note that the path may pass through a vertex more than once.
Answer:
#include<bits/stdc++.h>
#define R register
#define N 605
#define ll long long
const ll inf=1e18;
struct stu{
int v;
ll l;
stu(){}
stu(int vv,ll lr){v=vv,l=lr;}
};
std::vector<stu> vec[N];
ll dis[N][N];
int FR[N*N],TO[N*N],n,m;
ll W[N*N];
ll cfy[N];
bool bj[N*N];
int main(){
memset(dis,0x3f,sizeof(dis));
scanf(“%d%d”,&n,&m);
for(R int i=n;i;–i) dis[i][i]=0;
for(R int i=1;i<=m;++i){
scanf(“%d%d%d”,&FR[i],&TO[i],&W[i]);
dis[FR[i]][TO[i]]=std::min(dis[FR[i]][TO[i]],W[i]);
dis[TO[i]][FR[i]]=std::min(dis[TO[i]][FR[i]],W[i]);
}
for(R int k=1;k<=n;++k)
for(R int i=1;i<=n;++i)
for(R int j=1;j<=n;++j) dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]);
R int qq;
scanf(“%d”,&qq);
while(qq– >0){
R int uu,vv;R ll lr;
scanf(“%d%d%lld”,&uu,&vv,&lr);
vec[uu].push_back(stu(vv,lr));
vec[vv].push_back(stu(uu,lr));
}
for(R int u=1;u<=n;++u){
for(R int v=1;v<=n;++v) cfy[v]=-inf;
R int qwq=vec[u].size();
for(R int i=0;i<qwq;++i){
R int v=vec[u][i].v;
R ll l=vec[u][i].l;
for(R int y=1;y<=n;++y)
{
cfy[y]=std::max(cfy[y],l-dis[v][y]);
}
}
for(R int i=1;i<=m;++i){
R int x=FR[i],y=TO[i];
R ll e=W[i];
if(dis[u][x]+e<=cfy[y]){
bj[i] = 1;
}
}
}
R int ans=0;
for(R int i=1;i<=m;++i) if(bj[i]) ++ans;
std::cout<<ans << ‘\n’;
}
