【John的农场】

目录

【题目描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【说明/提示】

代码

---

【题目描述】

John的农场中有n块农田编号为1至n，农田之间有m条双向连通的道路，现在John想从农田s移动到农田t，问最少走多少距离。

【输入格式】

第一行四个由空格隔开的整数，分别表示n，m，s，t

之后的m行，每行三个正整数a，b，c，表示一条从a到b长度为c的边。

【输出格式】

一个整数表示从s到t的最短路长度。

数据保证至少存在一条道路。

【样例输入】

7 9 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

5 6 3

【样例输出】

7

【说明/提示】

1<=n<=2500,1<=m<=6500,

1<=a,b<=n,1<=c<=10000

代码

#include <bits/stdc++.h>
using namespace std;
struct node{
    int to,len; // 终点 距离
};
int n,m,w,x,y,z,s,t;
int d[2505],vis[2505];
vector<node>v[2505];
int main(){
    scanf("%d %d %d %d",&n,&m,&s,&t);
    for(int i=1;i<=n;i++) d[i]=1e9;
    d[s]=0;
    for(int i=0;i<m;i++){
        scanf("%d %d %d",&x,&y,&z);
        v[x].push_back((node){y,z});
        //顶点y，指向顶点x，距离z
        v[y].push_back((node){x,z});
    }
    for(int i=0;i<n;i++){
        int id=0,mn=1e9;
        for(int j=1;j<=n;j++){
            //选点的条件
            if(d[j]<mn&&vis[j]==0){ 
                mn=d[j],id=j;
            }
        }
        if(id==0) break; 
        vis[id]=1; 
        int to,len;
        for(int j=0;j<v[id].size();j++){
            to=v[id][j].to,len=v[id][j].len;
            //松弛的条件
            if(vis[to]==0 && d[id]+len < d[to]){ 
                d[to]=d[id]+len;
            }
        }
    }
    printf("%d\n",d[t]);
}