SPFA 40;Dijkstra AC.
这个Dijkstra是没问题的版本，有问题的参见：https://renjikai.com/luogu-p1339/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<cstring> #define ll long long #define pii pair<int,int> #define PINF 0x7fffffff #define NINF 0x80000000 using namespace std; int t, c, ts; struct edge { long long v, w; edge(int vv, int ww) { v = vv; w = ww; } bool operator < (const edge& e2) const{ return w > e2.w; } }; vector<edge> edges[100005]; long long dis[100005]; bool inqueue[100005]; bool visited[100005]; void SPFA() { queue<int> q; dis[ts] = 0; inqueue[ts] = true; q.push(ts); while (!q.empty()) { int node = q.front(); q.pop(); inqueue[node] = false; for (int i = 0; i < edges[node].size(); i++) { if (dis[edges[node][i].v] > dis[node] + edges[node][i].w) { dis[edges[node][i].v] = dis[node] + edges[node][i].w; if (!inqueue[edges[node][i].v])q.push(edges[node][i].v); } } } } void dijkstra() { priority_queue<edge> pq; dis[ts] = 0; pq.push(edge(ts,0)); while (!pq.empty()) { edge e = pq.top(); pq.pop(); if (visited[e.v])continue; visited[e.v] = true; //dis[e.v] = e.w; for (int i = 0; i < edges[e.v].size(); i++) { if (!visited[edges[e.v][i].v] && dis[edges[e.v][i].v] > dis[e.v] + edges[e.v][i].w) { //有可能存在一种情况：虽然没有轮到点i成为离已处理完毕的点集最近的点，但点i的距离值已经由其它处理中或处理完毕的点多次更新，所以松弛的第二个条件必须加入 dis[edges[e.v][i].v] = dis[e.v] + edges[e.v][i].w; pq.push(edge(edges[e.v][i].v, dis[edges[e.v][i].v])); } } } } int main() { ios::sync_with_stdio(false); cin >> t >> c >> ts; for (int i = 1; i <= c; i++) { int rs, re, ci; cin >> rs >> re >> ci; edges[rs].push_back(edge(re, ci)); } memset(dis, 0x7f, sizeof(dis)); //SPFA(); dijkstra(); for(int i=1;i<=t;i++)cout << dis[i]<<" "; } |
20190524更新，又写了一次Dijkstra ^v^
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include<iostream> #include<algorithm> #include<cstdio> #include<vector> #include<string> #include<queue> #include<cstring> #include<iomanip> using namespace std; int n, m, s; struct edge { int g, w; edge(int g, int w) :g(g), w(w) {} bool operator < (const edge& e1) const{ return this->w > e1.w; } }; vector<edge> edges[100005]; int dis[100005]; bool visited[100005]; void dijkstra() { memset(dis, 0x7f, sizeof(dis)); priority_queue<edge> pq; pq.push(edge(s, 0)); while (!pq.empty()) { edge node = pq.top(); pq.pop(); if (visited[node.g])continue; visited[node.g] = true; if (node.w >= dis[node.g])continue; dis[node.g] = node.w; for (int i = 0; i < edges[node.g].size(); i++) { edge & curE = edges[node.g][i]; if(!visited[curE.g])pq.push(edge(curE.g, node.w + curE.w)); } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s; for (int i = 1; i <= m; i++) { int f, g, w; cin >> f >> g >> w; edges[f].push_back(edge(g, w)); } dijkstra(); for (int i = 1; i <= n; i++) { if (dis[i] == 0x7f7f7f7f)cout << "2147483647 "; else cout << dis[i] << " "; } } |
