问一个问题
查看原帖
问一个问题
527212
邓不利多_henry楼主2023/1/9 16:31

P2866的AC代码为啥在DEV上RE了? (我使用的是新版红色DEV)

//#pragma GCC optimize(3)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <bitset>d\
#define ll long long
using namespace std;
const ll inf = 9223372036854775807;
ll n,m,s,e,N,num[100005];
struct mp{
	ll a[505][505];
	mp operator*(const mp x)const{
		mp c;
		memset(c.a,0x3f,sizeof(c.a));
		for(int i = 1;i <= N;i ++){
			for(int j = 1;j <= N;j ++){
				for(int k = 1;k <= N;k ++){
					c.a[i][j] = min(c.a[i][j],a[i][k] + x.a[k][j]);
				}
			}
		}
		return c;
	}
}dis,ans;
int main(){
	scanf("%lld%lld%lld%lld",&n,&m,&s,&e);
	ll x,y,z;
	memset(dis.a,0x3f,sizeof(dis.a));
	for(int i = 1;i <= m;i ++){
		scanf("%lld%lld%lld",&z,&x,&y);
		if(!num[x])num[x] = ++N;
		if(!num[y])num[y] = ++N;
		dis.a[num[x]][num[y]] = dis.a[num[y]][num[x]] = z;
	}
	n--;
	ans = dis;
	while(n){
		if(n&1){
			ans = ans * dis;
		}
		dis = dis*dis;
		n>>=1;
	}
	cout<<ans.a[num[s]][num[e]];
	return 0;
}
2023/1/9 16:31
加载中...