玄关求助邻接矩阵写法,不是为AC,只是想试试
查看原帖
玄关求助邻接矩阵写法,不是为AC,只是想试试
1057222
mountzhu楼主2024/11/11 21:09

除#1其他都不对

RE什么的倒没什么,只要在能对的范围内对了就行了

只是好奇为什么错了

真的没办法才求助的qaq

#include<bits/stdc++.h>
#define ll long long
#define INF 2147483647
#define pir pair
#define fir first
#define sec second
#define pq priority_queue
#define m_p make_pair
using namespace std;
const int N=1e4+5;
int n,m,k,s;
int mapi[N][N];
ll dis[N];bool vis[N];
int read(){
	char ch;int x=0,f=1;
	while(!isdigit(ch=getchar())){if(ch=='-')f=-1;}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
inline void dij(){
	pq<pir<int,int> > q;q.push(m_p(0,s));
	for(int i=1;i<=n;++i) dis[i]=INF;dis[s]=0;
	while(!q.empty()){
		pir<int,int> h=q.top();q.pop();
		if(vis[h.sec])continue;
		vis[h.sec]=1;
		for(int i=1;i<=n;++i){
			if(mapi[h.sec][i]!=-1){
				if(dis[h.sec]+mapi[h.sec][i]<dis[i]){
					dis[i]=dis[h.sec]+mapi[h.sec][i];
					if(!vis[i]) q.push(m_p(dis[i],i));
				}
			}
		}
	}
}
int main(){
	n=read(),m=read(),s=read();int u,v,w;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j) mapi[i][j]=-1;
	}for(int i=1;i<=m;++i){
		u=read(),v=read(),w=read();
		if(u==v) continue;
		if(mapi[u][v]==-1)mapi[u][v]=w;
		else mapi[u][v]=min(mapi[u][v],w);
	}dij();
	for(int i=1;i<=n;++i)printf("%lld ",dis[i]);
	return 0;
}

in: https://www.luogu.com.cn/paste/yooqaxq6 out: https://www.luogu.com.cn/paste/rk1g50mp

2024/11/11 21:09
加载中...