P1339 [USACO09OCT]Heat Wave G

Title Description

There is one  n  A little bit  m  Undirected graph of strip and edge , Request from  s  To  t  The shortest path length of .

Input format

First line four positive integers n,m,s,t. Next  mm  That's ok , Three positive integers per line u,v,w, Indicates a connection u,v, Long for  w  The edge of .

Output format

Output a line of integers , Answer .

I/o sample

Input #1 Copy

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

Output #1 Copy

7

explain / Tips

【 Data range 】
about  100\%100%  The data of ,1\le n \le 25001≤n≤2500,1\le m \le 62001≤m≤6200,1\le w \le 10001≤w≤1000.

【 Sample explanation 】
5 \to 6 \to 1 \to 45→6→1→4  It's the shortest path , The length is  3+1+3 = 73+1+3=7.

  The most basic dijastra template can be solved

ac Code

#include<bits/stdc++.h>
using namespace std;
#define inf 99999999
int n,m,s,t;
int a,b,l;
int v[2600][2600];
int dis[2600];
int book[2600];// Initializes the default as 0
int main()
{
    cin>>n>>m>>s>>t;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            if(i == j)v[i][j]=0;
            else v[i][j]=inf;
        }
    while(m--)
    {
        cin>>a>>b>>l;
        v[a][b]=l;
        v[b][a]=l;
    }
    for(int i=1;i<=n;i++)
        dis[i]=v[s][i];
    book[s]=1;
    for(int i=1;i<=n-1;i++)
    {
        int _min=inf,u;
        for(int j=1;j<=n;j++)// Find the point closest to the vertex 
        {
            if(book[j] == 0 && dis[j] < _min)
            {
                _min=dis[j];
                u=j;// And record its coordinates 
            }
        }
        book[u]=1;
        for(int j=0;j<=n;j++)
            dis[j]=min(dis[j],dis[u]+v[u][j]);// Compare s Point to j The distance and s Point to u Again from u To j Distance of , If the distance becomes shorter, replace 
    }
    cout<<dis[t];
    return 0;
}