https://vjudge.net/problem/HDU-2680
题意: 给出m 条边及其起始点终点与长度, 已知可以从 w 个起点出发, 求到某个终点 s 的最短路径注意是单向边 m<1e5,w<n<1000.
题解: 若每个起点都 kijkstra 一遍时间复杂度为 O((E+VlogV)*V), 会 TLE, 想了一下, 终点当初起点, 反向建边就可以了
坑点: 做图论习题一度因为没看到 directed,directional,wa 到怀疑 dijkstra 错了
ac 代码, 用的邻接表存图及优先队列 dijkstra
- #define _CRT_SECURE_NO_WARNINGS#include < iostream > #include < vector > #include < queue > #include < set > #include < stdio.h > using namespace std;
- const int maxn = 1e5 + 5;
- int n,
- m,
- ts[1005];
- //set ans;
- vector < pair < int,
- int > >E[maxn];
- int d[maxn];
- void init() {
- for (int i = 0; i < maxn; i++) E[i].clear(),
- d[i] = 1e9;
- }
- int main() {
- int s,
- t;
- while (cin >> n >> m >> s) {
- init();
- for (int i = 1; i <= m; i++) {
- int x,
- y,
- z;
- scanf("%d%d%d", &x, &y, &z);
- //E[x].push_back(make_pair(y, z));
- E[y].push_back(make_pair(x, z));
- }
- priority_queue < pair < int,
- int > >Q;
- d[s] = 0;
- Q.push(make_pair( - d[s], s));
- while (!Q.empty()) {
- int now = Q.top().second;
- Q.pop();
- for (int i = 0; i < E[now].size(); i++) {
- int v = E[now][i].first;
- if (d[v] > d[now] + E[now][i].second) {
- d[v] = d[now] + E[now][i].second;
- Q.push(make_pair( - d[v], v));
- }
- }
- }
- int ts;
- scanf("%d", &ts);
- int anss = 1e9;
- for (int i = 0; i < ts; i++) {
- scanf("%d", &t);
- anss = min(anss, d[t]);
- }
- if (anss == 1e9) cout << -1 << endl;
- else cout << anss << endl;
- }
- }
来源: http://www.bubuko.com/infodetail-2519026.html