[Codeforces 954D] Fight Against Traffic

[Codeforces 954D] Fight Against Traffic - 1600

문제 설명 : 

그래프에서 이미 길이 설치되어 있지 않은 두 노드 사이에 길을 추가했을 때, s에서 t로가는 최단거리의 값에 변함이 없도록 만드는 두 노드를 고르는 경우의 수를 구하는 문제이다.

풀이 : 

전처리로써 처음에 모든 노드에서 s까지의 거리, 모든 노드에서 t까지의 거리를 모두 구해놓는다. a에서 b로 가는 도로가 생긴다는 의미는 곧 a->b 최단거리가 1이 됨을 의미한다. 따라서 s->a거리, b->t 거리만 추가로 더해주기만 하면(역도 고려해야 하긴 하지만) 'a,b 노드에 길을 추가함으로써 최종 s->t로 가는 최단거리'를 구할 수 있다. 그래서 새롭게 구한 최단거리가 원래의 최단거리보다 더 짧아졌는지 그대로인지 값을 비교해보면 된다.

주의할 점 : 

-

배운 점 : 

a노드와 b노드 사이의 새로운 길을 추가하는 것은 곧 두 노드 사이의 최단거리가 1이 된다는 의미이다.

코드 :

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b){
        a=_a;
        b=_b;
    }
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 1009;
 
int V,E,s,t;
vector<int> graph[SIZE];
int ds[SIZE],dt[SIZE];
int adj[SIZE][SIZE]={0};
 
 
int main(){
    scanf("%d %d %d %d",&V,&E,&s,&t);
 
    for(int i=1 ; i<=V ; i++){
        ds[i]=dt[i]=SIZE;
    }
 
    for(int i=0 ; i<E ; i++){
        int u,v;    scanf("%d %d",&u,&v);
        adj[u][v]=adj[v][u]=1;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
 
    queue<int> q;
    ds[s]=0,dt[t]=0;
 
    q.push(s);
    while(!q.empty()){
        int cur=q.front();    q.pop();
        for(int next:graph[cur]){
            if(ds[next]>ds[cur]+1){
                ds[next]=ds[cur]+1;
                if(next!=t) q.push(next);
            }
        }
    }
 
    q.push(t);
    while(!q.empty()){
        int cur=q.front();    q.pop();
 
        for(int next:graph[cur]){
            if(dt[next]>dt[cur]+1){
                dt[next]=dt[cur]+1;
                if(next!=s) q.push(next);
            }
        }
    }
 
    int min_dist=ds[t];
    int ans=0;
    for(int i=1 ; i<=V ; i++){
        for(int j=i+1 ; j<=V ; j++){
            if(adj[i][j]==0)
                if(ds[i]+dt[j]+1<min_dist || dt[i]+ds[j]+1<min_dist);
                else ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}