每个输入包含一个测试用例。
输入的第一行包括四个正整数,表示位置个数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)。
对于每个用例,在单独的一行中输出从起点出发抵达快递位置再返回起点的最短距离。
3 3 1 3 1 2 3 2 3 3 3 1 1
7
#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; }