图正确,但无法正确更新最短路径。求大佬帮忙看下。
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;
}