Dijkstra未优化,求帮忙
  • 板块P2683 小岛
  • 楼主SweetAC
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/3/5 21:23
  • 上次更新2023/10/28 07:12:01
查看原帖
Dijkstra未优化,求帮忙
677316
SweetAC楼主2022/3/5 21:23

图正确,但无法正确更新最短路径。求大佬帮忙看下。

using namespace std;
const int maxn =200;
const int INF = 1e9;
int a[maxn][maxn],n,d[maxn];
bool vis[maxn]={0};
int out[maxn],k=0;
void Dijkstra(int t){
	fill(d,d+maxn,INF);
	d[t]=0;
	for(int i=1;i<=n;i++){
		int u=-1,MIN=INF;
		for(int j=1;j<=n;j++){
			if(vis[j]==0 && d[j]<MIN){
				u=j;
				MIN=d[j];
			}
		}
		if(u==-1) return;
		vis[u]=1;
		for(int v=1;v<=n;v++){
			if(vis[v]==0 && a[u][v]!=INF && d[u]+a[u][v]<d[v]){
				d[v]=d[u]+a[u][v];
			}
		}
	}
}

int main(){
    int m;
    cin>>n>>m;
    fill(a[0],a[0]+maxn*maxn,INF);
    for(int i=1;i<=m;i++)
	{
		int flag,t,s,u,v,e;
		cin>>flag;
		if(flag==1)
		 {
		 	cin>>u>>v>>e;
		 	if(e<a[u][v])
		 	{
		 		a[u][v]=e;
		 	    a[v][u]=e;
			}
		 }
		 if(flag==0)
		 {
		 	cin>>t>>s;
		 	Dijkstra(t);
		 	if(d[s]!=1e9)
		 	 out[k]=d[s];
		 	else
		 	 out[k]=-1;
		 	k++;
		 }
	}
//	for(int i=1;i<=n;i++)
//	 {
//	 	for(int j=1;j<=n;j++)
//	     printf("%-15d",a[i][j]);
//	    cout<<endl<<"??";
//	 }
//	 
//	for(int j=0;j<=n;j++)
//	     printf("%-15d",d[j]);  
    for(int i=0;i<k;i++)
     cout<<out[i]<<endl;
	return 0;	
}

2022/3/5 21:23
加载中...