关于Bellman-ford(玄关)
  • 板块学术版
  • 楼主Skywalker2187
  • 当前回复4
  • 已保存回复5
  • 发布时间2024/8/24 15:46
  • 上次更新2024/8/24 18:25:37
查看原帖
关于Bellman-ford(玄关)
906525
Skywalker2187楼主2024/8/24 15:46

rt,写出了以下代码,但本地运行无输出,洛谷ide上运行显示RE

码风奇特,凑合看
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <list>
#include <deque>
#include <bitset>
#include <iterator>
#include <cctype>
#include <sstream>
#include <utility>
#include <iomanip>
#include <limits>
#include <ctime>
#include <cstdlib>

// #define x first
// #define y second
#define mem(a,b) memset((a),(b),sizeof(a))

// typedef long long LL;
// typedef std::pair<int,int> PII;
// typedef std::vector<int> VEC;
// typedef std::queue<int> QUE;
// typedef std::stack<int> STK;
// typedef std::set<int> SET;
// typedef std::map<int,int> MAP;
// typedef std::priority_queue<int,std::vector<int>,std::greater<int> > P_Q;
// typedef std::priority_queue<int,std::vector<int>,std::less<int> > _P_Q;
// typedef std::bitset<L> BS;

// const int L=; // L!=1e9+10
const int inf=0x3f3f3f3f;
const int err=-1;
// const double eps=1e-8;
// const double pi=acos(-1.0);
const int N=1*1e2+10;
const int M=1*1e4+10;
// int dx[]={ 0 , 0 , 1 , -1 };
// int dy[]={ 1 , -1, 0 , 0  };
// LL mod=1e9+7;

#define I using
#define AK namespace
#define CSP_J2024 std
I AK CSP_J2024;

inline int read()
{
	int f=1;
	int x=0;
	char c=getchar();

	while(c<'0'||c>'9')
	{
		if(c=='-')
		{
			f=-1;
		}
		c=getchar();
	}
	
	while('0'<=c&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}

	return f*x;
}

inline void write(int x)
{
    if(x<0)
	{
        putchar('-');
		x=-x;
	}
    if(x>9)
	{
        write(x/10);
	}
    putchar(x%10+'0');
	
    return;
}

int n,m;

struct Edge
{
	int u;
	int v;
	int w;

	Edge(int ui,int vi,int wi):u(ui),v(vi),w(wi){}
};
vector<Edge> g;

int dist[N];
void init(int s)
{
	g.clear();

	mem(dist,inf);
	dist[s]=0;

	return;
}

inline void relax(int u,int v,int w)
{
	if(dist[v]>dist[u]+w)
	{
		dist[v]=dist[u]+w;
	}

	return;
}

inline int bellman_ford(int s,int t)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<m*2;j++)
		{
			relax(g[i].u,g[i].v,g[i].w);
		}
	}

	if(dist[t]==inf)
	{
		puts("***");
		return -1;
	}
		puts("***");
	return dist[t];
}

int main()
{
		puts("***");
	// #ifndef ONLINE_JUDGE
	// 	freopen(".in","r",stdin);
	// 	freopen(".out","w",stdout);
	// #endif

		puts("***");
	while(~scanf("%d%d",&n,&m))
	{
		if(n+m==0)
		{
			return 0;
		}

		init(1);
		for(int i=0;i<m;i++)
		{
			int u=read(),v=read(),w=read();
			Edge tmp(u,v,w);
			g.push_back(tmp);
			Edge _tmp(v,u,w);
			g.push_back(_tmp);
		}

		puts("***");
		write(bellman_ford(1,n));
		puts("");
	}
	
	return 0;
}

2024/8/24 15:46
加载中...