//https://www.luogu.com.cn/problem/P2683
//使用鄰接矩陣的dijsktra實(shí)現(xiàn)
//一直沒(méi)AC的原因居然是圖的初始化問(wèn)題？？
//fill函數(shù)到底怎么用的
#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;//小島的數(shù)目以及操作的數(shù)目
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個(gè)頂點(diǎn)
? ?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)
? ? ? ?{
? ? ? ? ? ?//沒(méi)找到這樣的邊即不連通
? ? ? ? ? ?return ;
? ? ? ?}
? ? ? ?visited[u]=true;
? ? ? ?for(int v=1;v<=n;v++)
? ? ? ?{
? ? ? ? ? ?//v沒(méi)有訪問(wèn)過(guò)且v可以到達(dá)且通過(guò)u的中轉(zhuǎn)使得到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
? ? ? ?{
? ? ? ? ? ?//是查詢(xún)操作
? ? ? ? ? ?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]);
? ? ? ? ? ?}
? ? ? ?}
? ?}
}