分类目录归档:图论

洛谷 P3381 【模板】最小费用最大流

参考链接:https://www.cnblogs.com/widerg/p/9394929.html

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
72
73
74
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int eN = 100005;
const int vN = 10005;
const int INF = 0x7f7f7f7f;
int n, m, s, t;
int ePtr = -1; //e的实际存储只能从偶数号顶点开始,奇数号顶点存储反向边
int to[eN << 1], nxt[eN << 1], value[eN << 1], cost[eN << 1];
int head[vN], dis[vN], minV[vN];
int preID[eN << 1], preNode[eN << 1];
bool inqueue[vN];
inline void createEdge(int u, int v, int w, int c) {
    to[++ePtr] = v;
    value[ePtr] = w;
    cost[ePtr] = c;
    nxt[ePtr] = head[u];
    head[u] = ePtr;
}
bool SPFA(int s, int t) {
    queue<int> q;
    memset(dis, 0x7f, sizeof(dis));
    memset(inqueue, false, sizeof(inqueue));
    memset(preID, -1, sizeof(preID));
    memset(preNode, -1, sizeof(preNode));
    memset(minV, 0x7f, sizeof(minV));
    dis[s] = 0;
    inqueue[s] = true;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        inqueue[x] = false;
        for (int i = head[x]; ~i; i = nxt[i]) {
            int dest = to[i];
            if (dis[dest] > dis[x] + cost[i] && value[i]) {
                dis[dest] = dis[x] + cost[i];
                minV[dest] = min(minV[x], value[i]);
                preID[dest] = i;
                preNode[dest] = x;
                if (!inqueue[dest]) {
                    inqueue[dest] = true;
                    q.push(dest);
                }
            }
        }
    }
    return dis[t] != INF;
}
void MinCostMaxFlow(int s, int t, int& maxflow, int& mincost) {
    while (SPFA(s, t)) {
        for (int i = t; i != s; i = preNode[i]) {
            value[preID[i]] -= minV[t];
            value[preID[i] ^ 1] += minV[t];
        }
        maxflow += minV[t];
        mincost += minV[t] * dis[t];
    }
}
int main() {
    memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, w, f;
        scanf("%d%d%d%d", &u, &v, &w, &f);
        createEdge(u, v, w, f);
        createEdge(v, u, 0, -f);//第0号边被占用,这条语句为反向边留下空间
    }
    int maxflow = 0, mincost = 0;
    MinCostMaxFlow(s, t, maxflow, mincost);
    printf("%d %d\n", maxflow, mincost);
}

洛谷 P3376 【模板】网络最大流

参考链接:https://www.cnblogs.com/widerg/p/9387909.html

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
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int eN = 100005;
const int vN = 10005;
const int INF = 0x7f7f7f7f;
int n, m, s, t;
int ePtr = -1; //e的实际存储只能从偶数号顶点开始,奇数号顶点存储反向边
int to[eN<<1], nxt[eN<<1], value[eN<<1];
int head[vN], dis[vN];
inline void createEdge(int u, int v, int w) {
    to[++ePtr] = v;
    value[ePtr] = w;
    nxt[ePtr] = head[u];
    head[u] = ePtr;
}
bool bfs(int s, int t) {
    queue<int> q;
    memset(dis, 0x7f, sizeof(dis));
    dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; ~i; i = nxt[i]) {
            int dest = to[i];
            if (dis[dest] == INF && value[i] != 0) {
                dis[dest] = dis[x] + 1;
                q.push(dest);
            }
        }
    }
    return dis[t] != INF;
}
int dfs(int x, int t, int maxflow) {
    if (x == t)return maxflow;
    int ans = 0;
    for (int i = head[x]; ~i; i = nxt[i]) {
        int dest = to[i];
        if (dis[dest] != dis[x] + 1 || value[i] == 0 || ans >= maxflow)continue;
        int f = dfs(dest, t, min(value[i], maxflow - ans));
        value[i] -= f;
        value[i ^ 1] += f;
        ans += f;
    }
    return ans;
}
int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t))ans += dfs(s, t, INF);
    return ans;
}
int main() {
    memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        createEdge(u, v, w);
        createEdge(v, u, 0);//第0号边被占用,这条语句为下一个边留下空间
    }
    printf("%d", dinic(s, t));
}

洛谷 P3386 【模板】二分图匹配

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
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<list>
#include<cmath>
#include<queue>
#include<unordered_set>
#include<unordered_map>
using namespace std;
int n, m, e;
vector<int> edges[2005];
bool visited[2005];
int match[2005];
bool biFind(int node) {
    if (visited[node])return false;
    visited[node] = true;
    for (int i = 0; i < edges[node].size(); i++) {
        if (!match[edges[node][i]] || biFind(match[edges[node][i]])) {
            match[node] = edges[node][i];
            match[edges[node][i]] = node;
            return true;
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> e;
    for (int i = 1; i <= e; i++) {
        int u, v;
        cin >> u >> v;
        if (u > n || v > m)continue;
        edges[u].push_back(v + n);
        edges[v + n].push_back(u);
    }
    int cnter = 0;
    for (int i = 1; i <= n; i++) {
        memset(visited, false, sizeof(visited));
        if (biFind(i))cnter++;
    }
    cout << cnter;
}

计蒜客 Random Access Iterator

原题链接:https://nanti.jisuanke.com/t/41392
竟然做出来一道这么复杂的概率+DFS+逆元题,开心到爆炸,特此发题解一篇^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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#define MOD 1000000007
#define ll long long
using namespace std;
int n;
int MDep;
vector<int> edges[1000005];
bool visited[1000005];
ll quickpow(ll a, ll b) {
    if (b == 0)return 1;
    ll re = quickpow(a, b / 2) % MOD;
    re = (re * re) % MOD;
    if (b % 2 == 1)re *= a % MOD;
    return re % MOD;
}
inline ll inv(ll x) {
    return quickpow(x, MOD - 2) % MOD;
}
inline ll chance1(ll TotNode) {
    ll ch = (inv(TotNode)) % MOD;
    return ch;
}
inline ll chance2(ll onceCh,ll TotNode) {
    ll onceNonch = (1ll-onceCh+MOD) % MOD;
    ll nonch = quickpow(onceNonch, TotNode);
    ll fin = (1ll - nonch + MOD) % MOD;
    return fin;
}
int dfsMaxDep(int node) {
    int maxDep = 1;
    bool hasChild = false;
    visited[node] = true;
    for (int i = 0; i < edges[node].size(); i++) {
        if (visited[edges[node][i]])continue;
        hasChild = true;
        maxDep = max(maxDep, dfsMaxDep(edges[node][i]) + 1);
    }
    return maxDep;
}
ll dfsChance(int depth,int node){
    if (depth == MDep)return 1;
    ll ch = 0,sCh=chance1(node==1?edges[node].size(): edges[node].size()-1);
    visited[node] = true;
    for (int i = 0; i < edges[node].size(); i++) {
        if (visited[edges[node][i]])continue;
        ll CurCH = dfsChance(depth + 1, edges[node][i]);
        if (CurCH) {
            ch += (CurCH * sCh) % MOD;
            ch %= MOD;
        }
    }
    return chance2(ch, node == 1 ? edges[node].size() : edges[node].size() - 1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    MDep = dfsMaxDep(1);
    memset(visited, false, sizeof(visited));
    ll ch = dfsChance(1, 1);
    cout << ch;
}

洛谷 P1113 杂务

这题本来就是个拓扑排序,搞了半天竟然搞不出来,想了半天。。
一开始的想法是:搞拓扑排序,一轮一轮的扫描,每一轮出一个最大时间,把最大时间相加就好了,后来发现全WA,为什么呢?因为同一轮里出来的任务其实有可能是不互相依赖的。比如任务1时间需要10;任务2时间需要5;任务3需要在任务1之后,任务4需要在任务2之后。如果一轮一轮的扫描,那么必须10秒之后同时开始做任务3/4。而实际情况则应该是任务2,5个时间作完之后就可以做任务4了。根据失误我又想着反向建图,用DFS递归解决,对每个结点(及其之前节点)找其最大的所用时间,写出来AC了(对于本题,杂务 k(k>1)的准备工作只可能在杂务 1 至 k-1 中,如果没有这个要求,反向建图就很好)。但是其实我想多了。直接一开始的拓扑排序,顺着推就可以了。
DFS版:

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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,times[10005],inDegree[10005],f[10005];
vector<int> edges[10005];
vector<int> curTasks;
int dfs(int node){
    if(f[node]!=0)return f[node];
    if(edges[node].size()==0)return f[node]=times[node];
    int maxT=0;
    for(int i=0;i<edges[node].size();i++){
        maxT=max(maxT,dfs(edges[node][i]));
    }
    return f[node]=maxT+times[node];
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        int v;
        cin>>v>>times[i];
        while(1){
            cin>>v;
            if(v==0)break;
            edges[i].push_back(v);
            inDegree[v]++;
        }
    }
    int maxTime=0;
    for(int i=1;i<=n;i++){
        if(inDegree[i]==0)maxTime=max(maxTime,dfs(i));
    }
    cout<<maxTime;
}

正常版:

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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,times[10005],inDegree[10005],allTimes[10005];
vector<int> edges[10005];
int sumTime=0;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        int v;
        cin>>v>>times[i];
        while(1){
            cin>>v;
            if(v==0)break;
            edges[v].push_back(i);
            inDegree[i]++;
        }
    }
    int maxT=0;
    for(int i=1;i<=n;i++)if(inDegree[i]==0){
        allTimes[i]+=times[i];
        for(int j=0;j<edges[i].size();j++){
            allTimes[edges[i][j]]=max(allTimes[edges[i][j]],allTimes[i]);
            inDegree[edges[i][j]]--;
        }
        inDegree[i]--;
        maxT=max(maxT,allTimes[i]);
    }
    cout<<maxT;
}

洛谷 P1144 最短路计数

自己一开始写了个,才60分,效率不高,后来看了题解。
参考题解:https://www.luogu.org/blog/user43513/luo-gu-p1144-zui-duan-lu-ji-shuo-ti-xie
60分代码:

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
#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 1000000
#define MAXM 2000000
#define MOD 100003
using namespace std;
int n,m;
int v[MAXM+5],nxt[MAXM+5];
bool visited[MAXM+5];
int fst[MAXN+5];
int dis[MAXN+5];
int cnter[MAXN+5];
int edgePtr=0;
void edgePush(int s,int e){
    edgePtr++;
    nxt[edgePtr]=fst[s];
    v[edgePtr]=e;
    fst[s]=edgePtr;
}
void SP(){
    memset(visited,false,sizeof(visited));
    memset(dis,0x7f,sizeof(dis));
    queue<int> q,qd;
    q.push(1);qd.push(0);
    while(!q.empty()){
        int node=q.front(),dist=qd.front();
        q.pop();qd.pop();
        if(visited[node])continue;
        visited[node]=true;
        dis[node]=dist;
        for(int e=fst[node];e!=-1;e=nxt[e]){
            if(!visited[v[e]]&&dis[v[e]]>dis[node]+1){
                dis[v[e]]=dis[node]+1;
                q.push(v[e]);qd.push(dis[v[e]]);
            }
        }
    }
}
void DFS(int node,int dist){
    if(dist!=dis[node])return;
    cnter[node]++;
    cnter[node]%=MOD;
    for(int e=fst[node];e!=-1;e=nxt[e]){
        if(visited[e])continue;
        visited[e]=true;
        DFS(v[e],dist+1);
        visited[e]=false;
    }
}
int main(){
    memset(fst,-1,sizeof(fst));
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(x==y)continue;
        edgePush(x,y);
        edgePush(y,x);
    }
    SP();
    memset(visited,false,sizeof(visited));
    DFS(1,0);
    for(int i=1;i<=n;i++)cout<<cnter[i]<<endl;
}

100分的:

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
#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 1000000
#define MAXM 2000000
#define MOD 100003
using namespace std;
int n,m;
int v[MAXM+5],nxt[MAXM+5];
bool visited[MAXM+5];
int fst[MAXN+5];
int dis[MAXN+5];
int cnter[MAXN+5];
int edgePtr=0;
void edgePush(int s,int e){
    edgePtr++;
    nxt[edgePtr]=fst[s];
    v[edgePtr]=e;
    fst[s]=edgePtr;
}
void SP(){
    memset(visited,false,sizeof(visited));
    memset(dis,0x7f,sizeof(dis));
    queue<int> q,qd;
    q.push(1);qd.push(0);
    cnter[1]=1;
    while(!q.empty()){
        int node=q.front(),dist=qd.front();
        q.pop();qd.pop();
        if(visited[node])continue;
        visited[node]=true;
        dis[node]=dist;
        for(int e=fst[node];e!=-1;e=nxt[e]){
            if(!visited[v[e]]&&dis[v[e]]>dis[node]+1){
                dis[v[e]]=dis[node]+1;
                q.push(v[e]);qd.push(dis[v[e]]);
                cnter[v[e]]+=cnter[node];
                cnter[v[e]]%=MOD;
            }else if(dis[v[e]]==dis[node]+1){
                cnter[v[e]]+=cnter[node];
                cnter[v[e]]%=MOD;
            }
        }
    }
}
int main(){
    memset(fst,-1,sizeof(fst));
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(x==y)continue;
        edgePush(x,y);
        edgePush(y,x);
    }
    SP();
    for(int i=1;i<=n;i++)cout<<cnter[i]<<endl;
}

洛谷 P1346 电车

基本上是裸的最短路,是第一个不用扳道岔的边长就是0,后面的需要扳道岔的长度就是1。然后愉快的套一个Dijkstra板子就可以了。

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
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n,a,b;
struct edge{
    int v,w;
    edge(int vv,int ww){v=vv;w=ww;}
    bool operator < (const edge& e2) const{
        return w>e2.w;
    }
};
vector<edge> edges[105];
priority_queue<edge> pq;
bool visited[105];
int dis[105];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        for(int j=1;j<=t;j++){
            int v;
            cin>>v;
            if(j==1)edges[i].push_back(edge(v,0));
            else edges[i].push_back(edge(v,1));
        }
    }
    //Dijkstra
    memset(dis,0x7f,sizeof(dis));
    pq.push(edge(a,0));
    while(!pq.empty()){
        edge cur=pq.top();
        pq.pop();
        if(visited[cur.v])continue;
        visited[cur.v]=true;
        dis[cur.v]=cur.w;
        for(int i=0;i<edges[cur.v].size();i++){
            if(!visited[edges[cur.v][i].v]&&dis[edges[cur.v][i].v]>dis[cur.v]+edges[cur.v][i].w){
                dis[edges[cur.v][i].v]=dis[cur.v]+edges[cur.v][i].w;
                pq.push(edge(edges[cur.v][i].v,dis[edges[cur.v][i].v]));
            }
        }
    }
    if(dis[b]!=0x7f7f7f7f)cout<<dis[b];
    else cout<<-1;
}

洛谷 P1991 无线通讯网

这道题很显然能够看出,只需找出与卫星电话数相等的联通块数,然后取联通块里的最大边就可以了。但是我想不出来怎么好写。
看过题解之后,经题解提醒“树的性质:删掉n条边一定出现n+1个连通块”,这样就好做了。

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int s, p;
struct edge {
    int u, v;
    double w;
    bool operator < (const edge& e2) const {
        return w < e2.w;
    }
}edges[125000];
struct point {
    int x, y;
}points[505];
int father[505];
int _find(int x) {
    if (father[x] == 0)return x;
    return father[x] = _find(father[x]);
}
bool _union(int x, int y) {
    x = _find(x); y = _find(y);
    if (x == y)return false;
    father[x] = y;
    return true;
}
inline double dis(int x1, int y1, int x2, int y2) {
    return sqrt((double)((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2)));
}
int main() {
    //ios::sync_with_stdio(false);
    cin >> s >> p;
    for (int i = 1; i <= p; i++) {
        cin >> points[i].x >> points[i].y;
    }
    int ePtr = 0;
    for (int i = 1; i <= p; i++) {
        for (int j = i + 1; j <= p; j++) {
            ePtr++;
            edges[ePtr].u = i;
            edges[ePtr].v = j;
            edges[ePtr].w = dis(points[i].x, points[i].y, points[j].x, points[j].y);
        }
    }
    sort(edges + 1, edges + ePtr + 1);
    int cnter = 0;
    for (int i = 1; i <= ePtr; i++) {
        if (_union(edges[i].u, edges[i].v)) {
            cnter++;
        }
        if (cnter == p - 1 - (s - 1)) {
            printf("%.2lf", edges[i].w);
            break;
        }
    }
}

洛谷 P4779 【模板】单源最短路径(标准版)

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] << " ";
    }
}