华东交通大学2018年ACM“双基”程序设计竞赛 K

MIKU酱是个玩游戏氪金的人，游戏公司给她制定了新的规则，如果想从关卡i到关卡j，你需要交一些钱就可以了，但同时，MIKU酱的爸爸zjw很爱她，所以她可以每过一关就向她爸要一次钱，但她爸每次给他的钱是固定的，MIKU酱是个不会节省的女孩，哪怕每次多出来的钱，她也会拿去买肥宅快乐水，所以每次要的钱一定花完，因为MIKU酱不想挨骂，所以希望每次他爸给她的钱最少。

tips（到达第n关即通过，每到达一关一定能通过这关）

输入描述:

多组输入，每个样例第一行输入两个整数n,m(2<=n<=200,1<=m<=1000)表示关卡和规则的数量，接下来m行规则，每行输入x,y,w（w<=1000）,表示从关卡x到y需要缴纳w的费用，保证题目有解，不会出现x=y的情况

输出描述:

输出一行，代表最少的钱

示例1

输入

复制

输出

复制

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <cmath>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 #define  ll long long

 #define  P pair<int,int>

 #define  ph   push_back

 const int inf=0x3f3f3f3f;

 int n,m,x,y,w;

 const int N =;

 int dis[N];

 vector<P>ve[N];

 void  init(){

     for(int i=;i<N;i++) {

         dis[i]=inf;

         ve[i].clear();

     }

 }

 int  bfs(int sta){

     priority_queue<P,vector<P>,greater<P> >q;

     dis[sta] =;

     q.push(P(,sta));

     while(!q.empty()){

         P p =q.top();

         q.pop();

         int fi =p.first,se=p.second;//fi：最短路径上到se位置的题目答案

         if(se==n) return  fi;

         for(int i=;i<ve[se].size();i++){

             P pp=ve[se][i];

             int ff=pp.first,ss=pp.second;

             if(dis[ff]>max(ss,fi)){

                 dis[ff]=max(ss,fi);//变小了

                 q.push(P(dis[ff],ff));

             }

         }

     }

     return  inf;

 }

 int  main()

 {

     while(~scanf("%d%d",&n,&m)){

         init();

         for(int  i=;i<m;i++){

             scanf("%d%d%d",&x,&y,&w);

             ve[x].ph(P(y,w));

         }

         int xx = bfs();

         printf("%d\n",xx);

     }

     return ;

 }

巴特西

华东交通大学2018年ACM“双基”程序设计竞赛 K

输入描述:

输出描述:

输入

输出

最新文章

热门文章