首页 > 代码库 > hdu 2680 (Dijkstra)

hdu 2680 (Dijkstra)

2024-07-08 07:06:01   217人阅读

快放暑假了，训练又要开始了。先从熟悉的图论开始做吧。

题意：一张有向图中有若干起点一个终点，让你算最短路，方法很简单只需人为加一个起点指向所有起点让后距离为0即可。

代码如下：

 1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #include <set> 5 #include <iostream> 6 #include <queue> 7 #include <map> 8 #include <math.h> 9 #include <string>10 #define MP(a, b) make_pair(a, b)11 #define PB(a) push_back(a)12 using namespace std;13 14 typedef pair<int, int> pii;15 const int LEN = 1010;16 const int INF = 0x3f3f3f3f;17 vector<pii> Map[LEN];18 int n, m, dis[LEN];19 20 void Dijkstra(int vex){21     int vis[LEN] = {0};22     priority_queue<pii, vector<pii>, greater<pii> > q;23     for(int i=0; i<=n; i++) dis[i] = INF;24     dis[vex] = 0;25     q.push(MP(dis[vex], vex));26     while(!q.empty()){27         pii nvex = q.top(); q.pop();28         int nv = nvex.second;29         if(vis[nv]) continue;30         vis[nv] = 1;31         for(int i=0; i<Map[nv].size(); i++){32             int x = Map[nv][i].first, y = Map[nv][i].second;33             if(dis[x] > dis[nv] + y){34                 dis[x] = dis[nv] + y;35                 q.push(MP(dis[x], x));36             }    37         }38     }39 }40 41 int main()42 {43 //    freopen("in.txt", "r", stdin);44 45     int a, b, c, tn, s, e;46     while(scanf("%d%d%d", &n, &m, &e)!=EOF){47         for(int i=0; i<LEN; i++) Map[i].clear();48         for(int i=0; i<m; i++){49             scanf("%d%d%d", &a, &b, &c);50             Map[a].PB(MP(b, c));51         }52         scanf("%d", &tn);53         for(int i=0; i<tn; i++){54             scanf("%d", &s);55             Map[0].PB(MP(s, 0));56         }57         Dijkstra(0);58         if(dis[e] != INF) printf("%d\n", dis[e]);59         else puts("-1");60     }61     return 0;62 }
View Code

 


联系
我们