全部RE,求助
查看原帖
全部RE,求助
153002
sm蒟蒻hhj楼主2020/9/18 13:51

改了好多次了啊

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

const int INF = 0x7fffffff;

const int noway = pow(2, 31) - 1;

struct edge
{
	int e, v;
};

vector<edge> sid[10008];

int n, m, s;

int u, v, w;

int dis[10008];

int SPFA(int b)
{
	queue<int> q;
	bool inqueue[10008] = {0};
	for (register int i = 0; i < 10007; ++i) dis[i] = INF;
	dis[b] = 0;
	q.push(b);
	inqueue[b] = 1;
	while(!q.empty())
	{
		int now = q.front();
		q.pop();
		inqueue[now] = 0;
		for (register int i = 0; i < sid[now].size(); ++i)
		{
			edge to = sid[now][i];
			if (dis[now] + to.v < dis[to.e])
			{
				dis[to.e] = dis[now] + to.v;
				if (!inqueue[to.e])
				{
					q.push(to.e);
					inqueue[to.e] = 1;
				}
			}
		}
	}
}

int main()
{
	cin >> n >> m >> s;
	for (register int i = 1; i <= m; ++i)
	{
		cin >> u >> v >> w;
		edge tmp;
		tmp.e = v, tmp.v = w;
		sid[u].push_back(tmp);
	}
	SPFA(s);
	for (register int i = 1; i <= n; ++i)
		cout << dis[i] << " ";
	
	
	return 0;
}
2020/9/18 13:51
加载中...