牛牛取快递

[编程题]牛牛取快递

热度指数：836 时间限制：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

输入

输出

算法知识视频讲解

勇敢牛牛，不怕困难！

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF 0x3f3f3f3f
#define not !
#define and &&

typedef struct {
  int to;     // 邻接点的编号 
  int next;   // 下一个邻接点的下标
  int weight; // 邻接点的权重
} Edge;

void addEdge(int* head, Edge* edges, const int u, const int v, const int w, int idx) {
  (*(edges + idx)).next = *(head + u);
  (*(edges + idx)).to = v;
  (*(edges + idx)).weight = w;
  *(head + u) = idx; 
}

void printAdjList(const int n, int* head, Edge* edges) {
  int i, u, v, w;
  for (u = 1; u <= n; ++u) {
    fprintf(stdout, "vertex %d: [  ", u);
    for (i = *(head + u); i; i = (*(edges + i)).next) {
      v = (*(edges + i)).to, w = (*(edges + i)).weight; 
      fprintf(stdout, "(%d, %d)  ", v, w);
    }
    fputs("]\n", stdout);
  }
  fputc(10, stdout);
}
  
// 荷兰科学家-迪杰斯特拉算法
int dijkstra_algorithm(int* head, Edge* edges, const int n, int start, int target) {
  
  int dists[n + 1]; 
  int visited[n + 1];
  memset(dists, INF, sizeof dists);
  memset(visited, 0x0000, sizeof visited);
  *(dists + start) = 0; // 源点到源点的距离为0
  
  int i, t, u, v, w, min_dist, selected;
  for (t = 0; t < n - 1; ++t) {
    // step 1
    min_dist = INF, selected = -1;
    for (u = 1; u <= n; ++u) {
      if (not *(visited + u) and *(dists + u) < min_dist) {
        min_dist = *(dists + u);
        selected = u;
      }
    }
    
    // step 2 加入已选顶点集合
    if (selected == -1) break;
    *(visited + selected) = 1;
    
    // step 3 进行松驰操作 
    for (i = *(head + selected); i; i = (*(edges + i)).next) {
      v = (*(edges + i)).to, w = (*(edges + i)).weight; 
      if (*(visited + v)) continue;
      if (*(dists + selected) + w < *(dists + v))
        *(dists + v) = *(dists + selected) + w;
    }
  }
    
  return *(dists + target);
}

int main(const int argc, const char** argv) {
  int n, m, s, t;
  fscanf(stdin, "%d %d %d %d", &n, &m, &s, &t);
  
  int head[n + 1];
  Edge edges[m + 1]; // directed graph
  memset(head, 0x0000, sizeof head);
  
  int i, u, v, w;
  for (i = 1; i <= m; ++i) {
    fscanf(stdin, "%d %d %d", &u, &v, &w);
    addEdge(head, edges, u, v, w, i);
  }
  
  // printAdjList(n, head, edges);
  
  int dist = dijkstra_algorithm(head, edges, n, s, t) 
           + dijkstra_algorithm(head, edges, n, t, s);
  
  return fprintf(stdout, "%d", dist), 0;
}

发表于 2021-07-17 20:09:17 回复(0)