牛牛取快递

[编程题]牛牛取快递

热度指数：330 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛的快递到了，他迫不及待地想去取快递，但是天气太热了，以至于牛牛不想在烈日下多走一步。他找来了你，请你帮他规划一下，他最少要走多少距离才能取回快递。

输入描述:

每个输入包含一个测试用例。
输入的第一行包括四个正整数，表示位置个数N(2<=N<=10000)，道路条数M(1<=M<=100000)，起点位置编号S(1<=S<=N)和快递位置编号T(1<=T<=N)。位置编号从1到N，道路是单向的。数据保证S≠T，保证至少存在一个方案可以从起点位置出发到达快递位置再返回起点位置。
接下来M行，每行包含三个正整数，表示当前道路的起始位置的编号U(1<=U<=N)，当前道路通往的位置的编号V(1<=V<=N)和当前道路的距离D(1<=D<=1000)。

输出描述:

对于每个用例，在单独的一行中输出从起点出发抵达快递位置再返回起点的最短距离。

示例1

输入

输出

算法知识视频讲解

黑莓婆婆

Dijkstra 算法

#include<bits/stdc++.h>
using namespace std;

struct E {
    int v;
    int d;
    E(int _v, int _d): v(_v), d(_d) {}
    bool operator < (const E& T) const {
        return d > T.d;
    }
};

int n;
vector<vector<E> > G;  // 存储每个结点的每条边

int calc(int s, int t) {
    // 计算从 s 到 t 的最短距离
    // Dijkstra 算法
    vector<bool> visited(n + 1);
    priority_queue<E> Q;
    Q.push(E(s, 0));
    while (!Q.empty()) {
        int u = Q.top().v;
        int d = Q.top().d;
        Q.pop();
        if (u == t) return d;
        if (visited[u]) continue;
        visited[u] = true;
        for (auto& tmp : G[u]) {
            if (visited[tmp.v]) continue;
            Q.push(E(tmp.v, d + tmp.d));
        }
    }
    return 0;
}

int main() {
    int m, s, t;
    cin >> n >> m >> s >> t;
    G.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        G[u].push_back(E(v, d));
    }
    cout << calc(s, t) + calc(t, s) << endl;
    return 0;
}

发表于 2021-08-10 20:55:02 回复(0)

C/C++

pein531

由于必须经过快递站，因此先走当前位置到快递站的最短路，回来的时候再走快递站到出发位置的最短路即可。如此一来，跑两遍迪杰斯特拉算法即可。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

int n, m, s, t;
const int INF = 0x3f3f3f3f;

int dijkstra(unordered_map<int, vector<PII>>& graph, int src, int dest) {
    vector<int> dist(n + 1, INF);
    vector<bool> st(n + 1);
    dist[src] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({dist[src], src});
    while(!heap.empty()) {
        auto t = heap.top();
        heap.pop();
        int cur = t.second;
        if(st[cur]) continue;
        st[cur] = true;
        for(auto nex: graph[cur]) {
            int j = nex.second;
            if(dist[j] > dist[cur] + nex.first) {
                dist[j] = dist[cur] + nex.first;
                heap.push({dist[j], j});
            }
        }
    }
    return dist[dest];
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    unordered_map<int, vector<PII>> graph;
    for(int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[u].push_back({w, v});
    }
    int res1 = dijkstra(graph, s, t);
    int res2 = dijkstra(graph, t, s);
    printf("%d", res1 + res2);
    return 0;
}

发表于 2023-02-07 15:05:28 回复(0)

咸鱼哥666

#include<bits/stdc++.h>
using namespace std;
struct Edge{
    int to;
    int distance;
};

int spfa(int src, int des,vector<vector<Edge>>&graph,int N){
    vector<bool> visited(N+1,false);
    vector<int> dis(N+1,INT_MAX);
    dis[src]=0;
    queue<int> myque;
    myque.push(src);
    visited[src]=true;// 在队列中的节点
    while(!myque.empty()){
        int temp =myque.front();
        myque.pop();
        visited[temp]=false;
        for(auto node=graph[temp].begin();node!=graph[temp].end();node++){
            int to = node->to;
            if(dis[to]>dis[temp]+node->distance){
                dis[to]=dis[temp]+node->distance;
                if(!visited[to]){
                    visited[to]=true;
                    myque.push(to);
                }
            }
        }
    }
    return dis[des];
}
int main()
{
    int N,M,S,T;
    cin>>N>>M>>S>>T;
    vector<vector<Edge>> graph(N + 1);// 看一维数组的解法有点难受，可以用vector解
    //为什么用一维数组
    int i=1;
    for(int i = 0; i < M; i++) {
        int from, to, distance;
        cin >> from >> to >> distance;
        graph[from].push_back({to,distance});
    }
    cout<<spfa(S,T,graph,N)+spfa(T,S,graph,N)<<endl;
    return 0;
}

发表于 2021-08-08 17:55:29 回复(0)

123201904111607339

发表于 2021-07-28 11:54:45 回复(0)

牛客118490042号

模板题，y总的代码真的太强啦！！！

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6;
int h[N],e[N],w[N],ne[N],idx;
int dist[N];
bool st[N];
void add(int a,int b, int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx] =h[a];
    h[a] = idx ++;
}

int spfa(int start,int end)
{
    memset(dist ,0x3f,sizeof dist);
    dist[start] = 0;
    
    queue<int> q;
    q.push(start);st[start] =true;
    
    while(q.size())
    {
        auto t = q.front();q.pop();
        st[t] =false;
        for(int i =h[t]; i!=-1;i=ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                //q.push(j);
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    if(dist[end] == 0x3f3f3f3f) return -1;
    else return dist[end];
    
}

int main()
{
    int n,m,s,t;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    
    memset(h,-1,sizeof h);//不能忘记初始化h
    
    while(m -- )
    {
        int a,b,c;
        scanf("%d%d%d", &a, &b, &c);
        add(a,b,c);
    }
    cout<<spfa(s,t)+spfa(t,s)<<endl;
    return 0;
}

编辑于 2021-07-25 12:17:27 回复(0)