Dijkstra求最短路 I

給定一個n個點m條邊的有向圖，圖中可能存在重邊和自環，所有邊權均為正值。

請你求出1号點到n号點的最短距離，如果無法從1号點走到n号點，則輸出-1。

輸入格式

第一行包含整數n和m。

接下來m行每行包含三個整數x，y，z，表示存在一條從點x到點y的有向邊，邊長為z。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int inf = 0x3f3f3f3f;
int dis[100010];
int g[510][510];
int vis[100010];
int n,m;
void dijstra()
{
  for(int i = 1; i <= n; i++)
  dis[i] = inf;
  dis[1] = 0;
  for(int i = 1; i <= n; i++)
  {
    int t = -1;
    for(int j = 1; j <= n; j++)
    {
      if(!vis[j]&&(t == -1 || dis[j] < dis[t]))
      t = j;
    }
    vis[t] = 1;
    for(int i = 1; i <= n; i++)
    {
      dis[i] = min(dis[i],dis[t] + g[t][i]);
    }
  }
}

int main()
{

  scanf("%d%d",&n,&m);
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
    g[i][j] = i == j ? 0:inf;
  while(m--)
  {
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    g[x][y] = min(g[x][y],z);
  }
    memset(vis,0,sizeof(vis));
    
    
    dijstra();
    if(dis[n] < inf)
    printf("%d\n",dis[n]);
    else
    printf("-1\n");
}