P2683 小岛

//https://www.luogu.com.cn/problem/P2683
//使用邻接矩阵的dijsktra实现
//一直没AC的原因居然是图的初始化问题？？
//fill函数到底怎么用的
#include<cstdio>
#include<algorithm>
#include<climits>
using namespace std;
const int MAXV=1010;
int G[MAXV][MAXV];
bool visited[MAXV];
int dist[MAXV];
int n,m;//小岛的数目以及操作的数目
void Init()
{
   for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
           G[i][j]=INT_MAX;
}
void dijsktra(int s,int n)
{
   fill(dist,dist+n+1,INT_MAX);
   fill(visited,visited+n+1, false);
   dist[s]=0;
   visited[s]=true;
   for(int j=1;j<=n;j++)
   {
       if(G[s][j]!=INT_MAX)
       {
           dist[j]=G[s][j];
       }
   }
   //枚举剩下的n-1个顶点
   for(int i=0;i<n-1;i++)
   {
       int u=-1;
       int min=INT_MAX;
       //找最短边
       for(int j=1;j<=n;j++)
       {
           if(visited[j]==false&&dist[j]<min)
           {
               u=j;
               min=dist[j];
           }
       }
       if(u == -1)
       {
           //没找到这样的边即不连通
           return ;
       }
       visited[u]=true;
       for(int v=1;v<=n;v++)
       {
           //v没有访问过且v可以到达且通过u的中转使得到v的距离更短更新
           if(visited[v]==false&&G[u][v]!=INT_MAX&&dist[u]+G[u][v]<dist[v])
           {
               dist[v]=dist[u]+G[u][v];
           }
       }
   }
}
int main()
{
   scanf("%d%d",&n,&m);
   Init();
   for(int i=0;i<m;i++)
   {
       int k;
       scanf("%d",&k);
       if(k == 1)
       {
           //是插入操作
           int u,v,w;
           scanf("%d%d%d",&u,&v,&w);
           if(w<G[u][v])
           {
               //判重边
               G[u][v]=G[v][u]=w;
           }
       }
       else
       {
           //是查询操作
           int s,t;
           scanf("%d%d",&s,&t);
           dijsktra(s,n);
           if(dist[t] == INT_MAX)
           {
               printf("-1\n");
           }
           else
           {
               printf("%d\n",dist[t]);
           }
       }
   }
}