洛谷 - P1346 - 电车 - Dijkstra/01BFS

https://www.luogu.org/problem/P1346
使用最短路之前居然忘记清空了。

#include
using namespace std;
typedef long long ll;const int MAXN = 1005;int n, s, t;
int dis[MAXN];
bool vis[MAXN];
int G[MAXN][MAXN];const int INF = 0x3f3f3f3f;priority_queue >pq;
void Dijkstra(int s) {for(int i=1;i<=n;++i)dis[i]=INF;dis[s] = 0;pq.push({-dis[s], s});while(!pq.empty()) {int u = pq.top().second;pq.pop();if(vis[u])continue;/*printf("u=%d\n",u);for(int i = 1; i <= n; ++i) {printf(" %d", i, dis[i]);}puts("");*/vis[u] = 1;for(int v = 1; v <= n; ++v) {int w = G[u][v];if(!vis[v] && dis[u] + w < dis[v]) {dis[v] = dis[u] + w;pq.push({-dis[v], v});}}}
}int main() {
#ifdef Yinkufreopen("Yinku.in", "r", stdin);
#endif // Yinkuscanf("%d%d%d", &n, &s, &t);for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)G[i][j] = INF;for(int i = 1; i <= n; ++i)G[i][i] = 0;for(int u = 1; u <= n; ++u) {int k;scanf("%d", &k);for(int j = 1; j <= k; ++j) {int v;scanf("%d", &v);if(j == 1)G[u][v] = 0;elseG[u][v] = 1;}}Dijkstra(s);/*for(int i = 1; i <= n; ++i) {printf("%d: %d\n", i, dis[i]);}*/printf("%d\n", dis[t] < INF ? dis[t] : -1);return 0;
}

看了一下题解貌似还有更快的。

#include
using namespace std;
typedef long long ll;const int MAXN = 1005;int n, s, t;
int dis[MAXN];
bool vis[MAXN];
int G[MAXN][MAXN];const int INF = 0x3f3f3f3f;dequeq;
void BFS(int s) {for(int i = 1; i <= n; ++i)dis[i] = INF;dis[s] = 0;q.push_front(s);while(!q.empty()) {int u = q.front();q.pop_front();if(vis[u])continue;vis[u] = 1;for(int v = 1; v <= n; ++v) {if(vis[v])continue;int w = G[u][v];if(w == 0) {if(dis[u] < dis[v]) {dis[v] = dis[u];q.push_front(v);}} else if(w == 1) {if(dis[u] + 1 < dis[v]) {dis[v] = dis[u] + 1;q.push_back(v);}}}}
}int main() {
#ifdef Yinkufreopen("Yinku.in", "r", stdin);
#endif // Yinkuscanf("%d%d%d", &n, &s, &t);for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)G[i][j] = INF;for(int i = 1; i <= n; ++i)G[i][i] = 0;for(int u = 1; u <= n; ++u) {int k;scanf("%d", &k);for(int j = 1; j <= k; ++j) {int v;scanf("%d", &v);G[u][v] = (j != 1);}}BFS(s);printf("%d\n", dis[t] < INF ? dis[t] : -1);return 0;
}

那应该可以得到一个使得Dijkstra更快的办法，就是另外开一个队列，把u节点相连的距离为0的节点加入队列，每次优先从队列里面取，其次才从优先队列里面取。

这个01BFS是指有花费的边的权都一样，所以不需要优先队列，从u出发的能到的点假如有花费一定是出现在队尾的。

转载于:https://www.cnblogs.com/Yinku/p/11345393.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！