本文主要是介绍TOJ 4279 Barricade / dijkstra，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Barricade
描述
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 33 2
1 3
3 22 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");elseprintf("%d\n",dis[n]);}return 0;
}
这篇关于TOJ 4279 Barricade / dijkstra的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
