Til the Cows Come Home

传送门：https://vjudge.net/contest/363819#problem/F

题意

　　最短路的裸题，给出有n个点的无向图，要求求顶点1到n的最短路。

思路

　　直接上迪杰斯特拉，题目是多组输入！多组输入！输入的第一行是边数和点数！谨以此博客记录我敲个裸题wa了12发。

AC代码

#include<iostream>
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn=2e3+5;
const int inf=0x3f3f3f3f;
int n,c,tmp;
int m[maxn][maxn],d[maxn],vis[maxn];
void dij(int u,int n){
    d[u]=0;
    for(int i=1;i<=n;i++){
        int tmp=inf,k=1;
        for(int j=1;j<=n;j++){
            if(vis[j]==0&&d[j]<tmp){
                k=j;
                tmp=d[j];
            }
        } 
        vis[k]=1;
        for(int j=1;j<=n;j++){
            if(vis[j]==0&&tmp+m[k][j]<d[j]){
                d[j]=tmp+m[k][j];
            }
        }
    }
}

int main()
{
    while(cin>>c>>n){
        int u,v,w;
        memset(d,0x3f,sizeof(d));
        memset(m,0x3f,sizeof(m));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=c;i++){
            cin>>u>>v>>w;
            if(w<m[u][v])
                m[u][v]=m[v][u]=w;
        }
        dij(n);
        cout<<d[1]<<'
';
    }
    return 0;
}