题目链接 SPFA判断负环

我不知道为什么不要初始化。却通过了。

if(dist[j] > dist[t] + w[i])
{
    dist[j] = dist[t] + w[i];
    cnt[j] = cnt[t] + 1;
    if(cnt[j] >= n) return true;

    if(!st[j])
    {
        q.push(j);
        st[j] = true;
    }
}

这个if不加初始化应该会出错吧？？

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 1500010;
int h[N], e[N], w[N], ne[N], idx;
int n, m;

bool b[N];
int dist[N];

void add(int a, int b, int c){ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;}

int dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    heap.push({0, 1});

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int distance = t.first, ver = t.second;

        if(b[ver]) continue;
        b[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(distance + w[i] < dist[j])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    ios :: sync_with_stdio(false), cin.tie(0);
    memset(h, -1, sizeof h);

    cin >> n >> m;
    while(m --)
    {
        int a, b, c;

        cin >> a >> b >> c;
        add(a, b, c);
    }

    printf("%d\n", dijkstra());

    return 0;
}

dijkstra 算法 O(N ^ 2)

#include <bits/stdc++.h>
#define cin_Quick ios :: sync_with_stdio(false), cin.tie(0)
#define T true
#define F false

using namespace std;

typedef int I;
typedef bool B;

const I N = 510;

I g[N][N];
I n, m;

B b[N];
I dist[N];

I dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for(I i = 0; i < n - 1; i ++)
    {
        I t = -1;

        for(I j = 1; j <= n; j ++)
            if(!b[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        for(I j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        b[t] = T;
    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin_Quick;
    memset(g, 0x3f, sizeof g);

    cin >> n >> m;
    while(m --)
    {
        I a, b, w;

        cin >> a >> b >> w;
        g[a][b] = min(g[a][b], w);
    }

    printf("%d\n", dijkstra());

    return 0;
}

题目描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

样例

输入

3 3
1 2 2
2 3 1
1 3 4

输出

3

数据范围

1 ≤ n ≤ 500,
1 ≤ m ≤ 1e5,
图中涉及边长均不超过10000。

数据范围说明这是稠密图， 无负权边， 算法 —> dijkstra 算法。

朴素 dijkstra 算法时间复杂度：

$O(N ^ 2)$

C++ 代码

#include <bits/stdc++.h>
#define cin_Quick ios :: sync_with_stdio(false), cin.tie(0) 
#define T true
#define F false 

using namespace std;

typedef int I;
typedef bool B;

// ---------- 以上是减代码的 TYPEDEF 和 DEFINE （虽然有一点多余）----------

const I N = 510;

I g[N][N];
I n, m;

B b[N];  // 已确定最短路的点
I dist[N];

// 最短路开始！！

I dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;                           // 初始化 dist 数组

    for(I i = 0; i < n - 1; i ++)
    {
        I t = -1;

        for(I j = 1; j <= n; j ++)
            if(!b[j] && (t == -1 || dist[t] > dist[j]))  // 找出现在不在 b 数组中的， 距离最近的点
                t = j;

        for(I j = 1; j <= n; j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]); // 用 t 去更新其他的点

        b[t] = T;  // t 已确定
    }

    if(dist[n] == 0x3f3f3f3f) return -1;  // 和初始数相同， 说明 1 到 n 无最短路
    return dist[n];                       // 否则返回最短路长度
}

int main()
{
    cin_Quick;  // cin 加速
    memset(g, 0x3f, sizeof g); // 初始化 g 数组

    cin >> n >> m; 
    while(m --)
    {
        I a, b, w;

        cin >> a >> b >> w;
        g[a][b] = min(g[a][b], w);  // 由于重边的原因，只需要保留最短的一条边
    } // 输入

    printf("%d\n", dijkstra()); 

    return 0;
}// over

制作不易， 麻烦给颗小星星（￣ω￣）

题目描述

给定一个 n个点 m 条边的有向图，点的编号是 1 到 n ，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y) ，x 在 A 中都出现在 y 之前，则称 A是该图的一个拓扑序列。

样例

输入

3 3
1 2
2 3
1 3

输出

1 2 3

C++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef queue<int> ns;
typedef int I;

const I N = 100010;
I h[N], e[N], ne[N];
I idx;

I d[N];

I n, m;
ns ans;

void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }

bool topsort()
{
    ns q;
    I tt = -1;

    for(I i = 1; i <= n; i ++)
        if(!d[i])
            q.push(i), tt ++;

    while(q.size())
    {
        I t = q.front();
        ans.push(t);
        q.pop();

        for(I i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            d[j] --;
            if(!d[j]) q.push(j), tt ++;
        }
    }

    return tt == n - 1;
}

I main()
{
    ios::sync_with_stdio(false),cin.tie(0);

    memset(h, -1, sizeof h);

    cin >> n >> m;
    while(m --)
    {
        I a, b;

        cin >> a >> b;
        add(a, b);

        d[b] ++;
    }

    if(topsort())
    {
        for(I i = 0; i < n; i ++) printf("%d ", ans.front()), ans.pop();
    }
    else puts("-1");

    return 0;
}

看不懂别见怪
若不是error了， typedef 和 define 可能还会跟多， 见谅 ~(￣.￣)~ hh

核对了好几遍 找不出答案

#include <bits/stdc++.h>

using namespace std;

const int N = 50010;
int p[N], d[N];

int find(int x)
{
    if(p[x] != x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }

    return p[x];
}

int main()
{
    int n, k, res = 0;

    cin >> n >> k;

    for(int i = 1; i <= n; i ++) p[i] = i;

    while(k --)
    {
        int D;
        int x, y;

        cin >> D >> x >> y;

        if(x > n || y > n) res ++;
        else
        {
            int px = find(x), py = find(y);

            if(D == 1)
            {
                if(px == py && (d[x] - d[y]) % 3) res ++;
                else 
                {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
                if(px == py && (d[x] - d[y] - 1) % 3) res ++;
                else 
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }

    cout << res << endl;
    return 0;
}

求助!!

我这有什么问题吗??!! 有个测试点明明输出和答案一样, 它还WA!!!

#include <iostream>

using namespace std;

const int N =  100010;
int QuickStack[N];

int head;

void push(int x){ QuickStack[++ head] = x; }

void pop(){ head --; }

bool empty(){ return head == 0; }

int query(){ return QuickStack[head]; }

int main()
{
    ios :: sync_with_stdio(false),
    cin.tie(0), 
    cout.tie(0);

    int n;

    cin >> n;
    while(n --){
        string que;
        int x;

        cin >> que;

        if(que == "push") cin >> x, push(x);
        else if(que == "pop") pop();
        else if(que == "query") cout << query() << endl;
        else cout << (empty() ? "Yes" : "No") << endl;
    }

    return 0;
}