2013-team5/SPP

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 550;
const int M = 3000<<1;

int Case, n, m, w;
int tot, h[N], nxt[M], c[M], v[M];
int used[N], dis[N];
bool visit[N];

void add(int s, int t, int e) {
    v[tot] = t; c[tot] = e;
    nxt[tot] = h[s]; h[s] = tot++;
}

bool spfa(int s) {
    int u;
    queue <int> q; while(!q.empty())  q.pop();
    memset(visit, false, sizeof(visit));
    memset(used, 0, sizeof(used));
    for(int i = 1; i <= n; i++)  dis[i] = 0x1fffffff; dis[0] = 0;
    used[0] = 1;
    q.push(s);
    while(!q.empty()) {
        u = q.front(); q.pop();
        visit[u] = false;
        for(int p = h[u]; p != -1; p = nxt[p]) {
            if(dis[v[p]] > dis[u] + c[p]) {
                dis[v[p]] = dis[u] + c[p];
                if(!visit[v[p]]) {
                    visit[v[p]] = true;
                    q.push(v[p]);
                    used[v[p]]++;
                    if(used[v[p]] >= n)  return  true;
                }
            }
        }
    }
    return  false;
}

int main() {
    int s, t, e;
    scanf("%d", &Case);
    while(Case--) {
        scanf("%d%d%d", &n, &m, &w);
        memset(h, -1, sizeof(h)); tot = 0;
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &s, &t, &e);
            add(s, t, e);
            add(t, s, e);
        }
        for(int i = 0; i < w; i++) {
            scanf("%d%d%d", &s, &t, &e);
            add(s, t, -e);
        }
        for(int i = 1; i <= n; i++)  add(0, i, 0);
        if(spfa(0))  printf("YES\n");
        else  printf("NO\n");
    }
    return  0;
}
}}}

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 550;
const int M = 3000<<1;
int Case, n, m, w;
int tot, h[N], nxt[M], c[M], v[M];
int used[N], dis[N];
bool visit[N];
void add(int s, int t, int e) {
    v[tot] = t; c[tot] = e;
    nxt[tot] = h[s]; h[s] = tot++;
}
bool spfa(int s) {
    int u;
    queue <int> q; while(!q.empty())  q.pop();
    memset(visit, false, sizeof(visit));
    memset(used, 0, sizeof(used));
    for(int i = 1; i <= n; i++)  dis[i] = 0x1fffffff; dis[0] = 0;
    used[0] = 1;
    q.push(s);
    while(!q.empty()) {
        u = q.front(); q.pop();
        visit[u] = false;
        for(int p = h[u]; p != -1; p = nxt[p]) {
            if(dis[v[p]] > dis[u] + c[p]) {
                dis[v[p]] = dis[u] + c[p];
                if(!visit[v[p]]) {
                    visit[v[p]] = true;
                    q.push(v[p]);
                    used[v[p]]++;
                    if(used[v[p]] >= n)  return  true;
                }
            }
        }
    }
    return  false;
}
int main() {
    int s, t, e;
    scanf("%d", &Case);
    while(Case--) {
        scanf("%d%d%d", &n, &m, &w);
        memset(h, -1, sizeof(h)); tot = 0;
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &s, &t, &e);
            add(s, t, e);
            add(t, s, e);
        }
        for(int i = 0; i < w; i++) {
            scanf("%d%d%d", &s, &t, &e);
            add(s, t, -e);
        }
        for(int i = 1; i <= n; i++)  add(0, i, 0);
        if(spfa(0))  printf("YES\n");
        else  printf("NO\n");
    }
    return  0;
}