【模板】单源最短路1

C++ 解法, 执行用时: 16ms, 内存消耗: 2304KB, 提交时间: 2022-03-25

#include <bits/stdc++.h>

using namespace std;
const int N = 50005 * 2;
int h[N], ne[N], w[N], e[N], idx;
int dist[N];
int vis[N];
void add(int a, int b, int ww) {
    ne[idx] = h[a], e[idx] = b, w[idx] = ww , h[a] = idx++;
}
int n, m;
int spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    vis[1] = true;
    while(q.size()) {
        int top = q.front();
        q.pop(), vis[top] = false;
        for (int j = h[top]; j != -1; j = ne[j]) {
            int x = e[j];
            if (dist[x] > dist[top] + w[j]) {
                dist[x] = dist[top] + w[j];
                if (vis[x] == false) {
                    q.push(x);
                    vis[x] = true;
                }
            }
        }
    }
    
    return dist[n];
}
int main() {
    int a, b;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b, 1);
        add(b, a, 1);
    }
    int ans = spfa();
    if (ans > 0x3f3f3f3f/2) cout << -1 << endl;
    else cout << ans << endl;
    
    return 0;
}

C++ 解法, 执行用时: 16ms, 内存消耗: 2312KB, 提交时间: 2022-05-05

#include <bits/stdc++.h>

using namespace std;
const int N = 50005 * 2;
int h[N], ne[N], w[N], e[N], idx;
int dist[N];
int vis[N];
void add(int a, int b, int ww) {
    ne[idx] = h[a], e[idx] = b, w[idx] = ww, h[a] = idx++;
}
int n, m;
int spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    vis[1] = true;
    while (q.size()) {
        int top = q.front();
        q.pop(), vis[top] = false;
        for (int j = h[top]; j != -1; j = ne[j]) {
            int x = e[j];
            if (dist[x] > dist[top] + w[j]) {
                dist[x] = dist[top] + w[j];
                if (vis[x] == false) {
                    q.push(x);
                    vis[x] = true;
                }
            }
        }
    }
    return dist[n];
}
int main() {
    int a, b;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b, 1);
        add(b, a, 1);
    }
    int ans = spfa();
    if (ans > 0x3f3f3f3f / 2) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

C++ 解法, 执行用时: 17ms, 内存消耗: 1292KB, 提交时间: 2022-07-14

#include <bits/stdc++.h> // C++万能头文件
using namespace std;
static const auto io_sync_off = [](){ // lambda表达式
    std::ios::sync_with_stdio(false); // 解除与scanf()等函数的同步
    std::cin.tie(nullptr); // 解除cin和cout的绑定
    return nullptr;
}();

const int N = 5001;
int main() {
    vector<vector<int>> graph(N); // 邻接表
    int dis[N]; // 到每个节点的距离
    memset(dis, -1, sizeof(dis)); // 同时防止重复遍历
    int n, m;
    cin >> n >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    queue<int> q;
    q.push(1);
    dis[1] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : graph[u]) {
            if (dis[v] == -1) {
                q.push(v);
                dis[v] = dis[u] + 1;
            }
        }
    }
    cout << dis[n] << "\n";
    return 0;
}

C++ 解法, 执行用时: 17ms, 内存消耗: 1292KB, 提交时间: 2022-05-01

#include <cstdio>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

int n, m;
int small_step=INT_MAX;
int visited[5100];
vector<int> edge[5100];

struct node{
    int s;
    int step;
} Node;

bool judge(int id){
    if(visited[id]==1) return false;
    else return true;
}

int bfs(int start, int step){
    int start_id;
    int start_step;
    queue<node> save; 
    Node.s=start;
    Node.step=step;
    save.push(Node);
    visited[start]=1;
    while(!save.empty()){
        node temp = save.front();
        save.pop();
        start_id = temp.s;
        start_step = temp.step;
        if(start_id==n){
            return start_step;
        }
        for(int i=0; i<edge[start_id].size(); i++){
            if(judge(edge[start_id][i])){
                Node.s=edge[start_id][i];
                Node.step=start_step+1;
                save.push(Node);
                visited[edge[start_id][i]]=1;
            }
        }
    }
    return -1;
}

int main(){
    int u, v;
    scanf("%d %d", &n, &m);
    for(int i=0; i<m; i++){
        scanf("%d %d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    printf("%d\n", bfs(1, 0));
    return 0;
}

C++ 解法, 执行用时: 17ms, 内存消耗: 2304KB, 提交时间: 2022-03-31

/*#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=5010*2;
const int INF_MAX=10;
queue<int> q;
int n,m;
int g[N][N];
int dist[N];
bool dot[N];
int bfs(){
    q.push(1);
    dist[1]=0;
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        for(int i=n;i>=t+1;i--){  
                if(g[t][i]==1&&!dot[i]){
                    q.push(i);
                if(dist[i]!=-1) dist[i]=min(dist[t]+1,dist[i]);
                dist[i]=dist[t]+1;
                /*for(int k=1;k<=n;k++){
                    cout<<dist[k]<<" ";
                }
                    puts("");*/
                   /* if(i==n) break;
            }
        }
        dot[t]=true;
        if(dist[n]!=-1) break;
    }
    return dist[n];
}
int main(){
    cin>>n>>m;
    memset(dist,-1,sizeof(dist));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) g[i][j]=0;
            else g[i][j]=INF_MAX;
        }  
    }
    while(m--){
        int x,y;
        cin>>x>>y;
        g[x][y]=g[y][x]=1;
    }*/
    /*for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            printf("%d ",g[i][j]);
        }
        puts("");
    }
    for(int i=1;i<=n;i++){
        cout<<dist[i]<<" ";
    }*/
    /*int ans=bfs();
    cout<<ans<<endl;
    return 0;
}*/
#include <bits/stdc++.h>

using namespace std;
const int N = 50005 * 2;
int h[N], ne[N], w[N], e[N], idx;
int dist[N];
int vis[N];
void add(int a, int b, int ww) {
    ne[idx] = h[a], e[idx] = b, w[idx] = ww , h[a] = idx++;
}
int n, m;
int spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    vis[1] = true;
    while(q.size()) {
        int top = q.front();
        q.pop(), vis[top] = false;
        for (int j = h[top]; j != -1; j = ne[j]) {
            int x = e[j];
            if (dist[x] > dist[top] + w[j]) {
                dist[x] = dist[top] + w[j];
                if (vis[x] == false) {
                    q.push(x);
                    vis[x] = true;
                }
            }
        }
    }
    
    return dist[n];
}
int main() {
    int a, b;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b, 1);
        add(b, a, 1);
    }
    int ans = spfa();
    if (ans > 0x3f3f3f3f/2) cout << -1 << endl;
    else cout << ans << endl;
    
    return 0;
}

详情