codeforce 449 B 最短路

codeforce 449 B

题意： 一个无向图，给你两种边，一种边可以删除（全部从起点出发），问在不改变原来所有点最短路的情况下，能删最多多少条边。

解： 由于可删边都从起点出发，松弛时候也不会返回起点，所以只需要建立从起点到另一点的单向边，然后进行一遍spfa，初始所有点的最短路的值，

然后判断所有可删边，如果该边长比最短路的值长即可删，如果相等，再对到达的点进行判断，看能否由其他的边实现最短路，如果可以，即改变可以删除，判断完之后给该点标记，当下次有边指向他的时候可以直接删除。

注意 最短路距离 开 longlong 

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ; /// data over into -
const int inf = 0x3f3f3f3f ;
const int maxn = 200005 ;
const int maxm = 400005 ;
struct edge{
int u , v , w;
bool mark ; /// train = 1 , road = 0
};
vector<int> g[maxn] ;
vector<edge> Edge ;
int inq[maxn] ;
ll dis[maxn];
bool mark[maxm] ;
void addEdge(int u , int v , int w , bool mark){
edge e ;
e.mark = mark ;
e.u = u , e.v = v , e.w = w ;
Edge.push_back(e) ;
g[u].push_back(Edge.size() - 1) ;
}
void spfa(int u)
{
int i,k;
memset(dis , inf , sizeof(dis)) ;
memset(inq , 0 , sizeof(inq)) ;
dis[u] = 0 ; inq[u] = 1 ;
queue <int> q;
q.push(u);
while (! q.empty() ){
int t = q.front() ; q.pop() ;
inq[t] = 0 ;
for(k = 0 ; k < g[t].size() ; k ++){
edge e = Edge[ g[t][k] ];
if (dis[e.v] > dis[e.u] + e.w)
{
dis[e.v] = dis[e.u] + e.w;
if(! inq[e.v]){
inq[e.v] = 1 ;
q.push(e.v);
}
}
}
}
}
bool check(int x){
edge e ;
for(int i = 0 ; i < g[x].size() ; i ++ ){
e = Edge[g[x][i]] ;
//cout << g[x][i] << " " << num << endl ;
//if(g[x][i] == num + 1 || g[x][i] == num) continue ;
if(e.w + dis[e.v] == dis[x] )
return 1 ;
}
return 0 ;
}
int main(){
int n , m , k ;
scanf("%d %d %d" , &n , &m , &k) ;
int a , b , w ;
for(int i = 0 ; i < m ; i ++ ){
scanf("%d %d %d" , &a , &b , &w) ;
addEdge(a , b , w , 0) ;
addEdge(b , a , w , 0) ;
}
for(int i = 0 ; i < k ; i ++ ){
scanf("%d %d" , &a , &w) ;
addEdge(1 , a , w , 1) ;
}
spfa(1) ;
int ans = 0 ;
edge e ;
memset(mark , 0 , sizeof(mark)) ;
//for(int i = 1 ; i <= n ; i ++ ) cout << dis[i] << " " ; cout << endl ;
for(int i = 0 ; i < g[1].size() ; i ++ ){
if(Edge[g[1][i]].mark){
e = Edge[g[1][i]] ;
if(mark[e.v] || e.w > dis[e.v] ){
ans ++ ;
//mark[e.v] = 1 ;
}else{
ans += check(e.v) ;
mark[e.v] = 1 ;
}
}
}
printf("%dn" , ans) ;
return 0 ;
}
/*
2 2 3
1 2 2
2 1 3
2 1
2 2
2 3
5 5 3
1 2 1
2 3 2
1 3 3
3 4 4
1 5 5
3 5
4 5
5 5
*/

最后

以上就是重要方盒为你收集整理的codeforce 449 B 最短路的全部内容，希望文章能够帮你解决codeforce 449 B 最短路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。