【农场移动】

目录

【题目描述】

【输入格式】

【输出格式】

【输入样例】

【输出样例】

【说明/提示】

代码

---

【题目描述】

john的农场中有n块农田编号为1至n，农田之间有m条单向连通的道路，走每条路都会消耗体力，幸运的是，有时路上遇到朋友可以搭车，不仅不消耗体力，还可以休息恢复体力。问从s移动到t最少消耗多少体力。

【输入格式】

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

之后的m行，每行三个正整数x，y，z，表示一条从x到y长度为z的单向边，若z>0表示消耗体力，若z<0表示可以搭车并恢复-z体力。

【输出格式】

一个整数表示最少消耗的体力。

【输入样例】

5 5 1 5

1 2 5

1 3 7

3 5 1

1 4 10

4 5 -4

【输出样例】

6

【说明/提示】

1<=n,m<=100,1<=x,y,s,t<=n,-100<=z<=100,保证数据没有负环。

代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int from,to,len;
}a[15555];
int n,m,w,x,y,z,s,t;
int d[2505],cnt;
void add(int from,int to,int len){
    a[cnt].from=from,a[cnt].to=to,a[cnt].len=len;
    cnt++;
}
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);
        add(x,y,z);
    }
    int from,to,len;
    for(int k=0;k<n;k++){
        for(int i=0;i<cnt;i++){
            from=a[i].from,to=a[i].to,len=a[i].len;
            //边的松弛
			if(d[to]>d[from]+len){
                d[to]=d[from]+len;
            }
        }
    }
    printf("%d\n",d[t]);
}