TOJ 4279 Barricade / dijkstra

当前位置 : 首页 > 网页制作 > CSS > TOJ 4279 Barricade / dijkstra

TOJ 4279 Barricade / dijkstra

来源: 作者: 时间:2016-01-28 09:27
Barricade时间限制(普通 Java):1000MS 3000MS 运行内存限制:65536KByte描述GBQC国一共有N个城市,标号分别为1, 2, , N。N个城市间一共有M条单向通行的道路。不幸的是,GBQC国的城市1连续暴雨,使得
Barricade
时间限制(普通/):1000MS/3000MS     运行内存限制:65536KByte
 
描述
 
 
GBQC国一共有N个城市,标号分别为1, 2, …, N。N个城市间一共有M条单向通行的道路。
 
不幸的是,GBQC国的城市1连续暴雨,使得整个城市淹没在汪洋洪水中,于是GBQC国领导人小明决定让城市1的居民暂时移居到城市N,于是一场浩浩荡荡的搬迁运动开始了。
 
但还有一个问题需要解决,居民从城市1出发,如果走到某个城市时面对多条道路,那么城市1的居民就不知道该往哪个方向走了。
 
为了解决上述问题,GBQC国领导人决定在一些道路的入口处设置“禁止通行”的路障,以确保城市1的居民从城市1出发,途径每个城市时,都有且仅有一条路可供选择,这样城市1的居民就能顺利搬迁到城市N了。
 
    现在GBQC国领导人想知道最少需要设置几个路障呢?
 
 
输入
 
 
输入包含多组测试数据。
 
对于每组测试数据,第一行包含两个整数N(2<=N<=10^4), M(0<=M<=10^5),其中N、M的含义同上。接下来一共有M行,每行有三个整数x(1<=x<=N)、y(1<=y<=N),表示GBQC国有一条由城市x进入通向城市y的单向道路。
 
 
输出
 
 
对于每组测试数据,用一行输出一个整数表示最少需要设置几个路障。如果没办法从城市1出发走到城市N,则输出“-1”(不包括引号)。
 
样例输入
 
3 4
1 1
1 2
1 3
1 3
 
3 2
1 3
3 2
 
2 0
样例输出
 
3
0
-1
将每个点的出度-1作为权值 在求最短路
 
优先队列优化
 
 
#include <stdio.h>  
#include <string.h>  
#include <queue>  
#include <vector>  
using namespace std;  
struct node  
{  
    int end;  
    int dis;  
    bool friend operator <(node a,node b)  
    {  
        return a.dis > b.dis;  
    }  
};  
const int MAX = 10010;  
int n,m;  
int dis[MAX];  
int degree[MAX];  
vector <int> v[MAX];  
void dijkstra()  
{  
    int i;  
    for(i = 1;i <= n; i++)  
        dis[i] = 0x7fffffff;  
    dis[1] = 0;  
    node t;  
    t.end = 1;  
    t.dis = 0;  
    priority_queue <node> q;  
    q.push(t);  
    while(!q.empty())  
    {  
        t = q.top();  
        q.pop();  
        int len = v[t.end].size();  
        for(i = 0;i < len; i++)  
        {  
            node tt;  
            int k = v[t.end][i];  
            if(dis[k] > t.dis + v[t.end].size() - 1)  
            {  
                dis[k] = t.dis + v[t.end].size() - 1;  
                tt.end = k;  
                tt.dis = dis[k];  
                q.push(tt);  
            }  
        }  
    }  
}  
int main()  
{  
    node x;  
    int s,e,i;  
    while(scanf("%d %d",&n,&m)!=EOF)  
    {  
        //memset(degree,0,sizeof())  
        for(i = 1;i <= n; i++)  
            v[i].clear();  
        while(m--)  
        {  
            scanf("%d %d",&s,&e);  
            v[s].push_back(e);  
        }  
        dijkstra();  
        if(dis[n] == 0x7fffffff)  
            puts("-1");  
        else  
            printf("%d\n",dis[n]);  
    }  
    return 0;  
}  

 

 
Tag:
网友评论

<