51Nod 1459：迷宫游戏（最短路）-白红宇

51Nod 1459：迷宫游戏（最短路）

阅读量：6848 次

发布时间：2019-06-26

本文共 1574 字，大约阅读时间需要 5 分钟。

基准时间限制：1 秒空间限制：131072 KB 分值: 0

关注

你来到一个迷宫前。该迷宫由若干个房间组成，每个房间都有一个得分，第一次进入这个房间，你就可以得到这个分数。还有若干双向道路连结这些房间，你沿着这些道路从一个房间走到另外一个房间需要一些时间。游戏规定了你的起点和终点房间，你首要目标是从起点尽快到达终点，在满足首要目标的前提下，使得你的得分总和尽可能大。现在问题来了，给定房间、道路、分数、起点和终点等全部信息，你能计算在尽快离开迷宫的前提下，你的最大得分是多少么？

Input

第一行4个整数n (<=500), m, start, end。n表示房间的个数，房间编号从0到(n - 1)，m表示道路数,任意两个房间之间最多只有一条道路，start和end表示起点和终点房间的编号。

 第二行包含n个空格分隔的正整数(不超过600)，表示进入每个房间你的得分。
 再接下来m行，每行3个空格分隔的整数x, y, z (0<z<=200)表示道路,表示从房间x到房间y(双向)的道路,注意，最多只有一条道路连结两个房间, 你需要的时间为z。
 输入保证从start到end至少有一条路径。

Output

一行，两个空格分隔的整数，第一个表示你最少需要的时间，第二个表示你在最少时间前提下可以获得的最大得分。

Input示例

3 2 0 21 2 30 1 101 2 11

Output示例

21 6

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define ll long long#define ms(a) memset(a,0,sizeof(a))#define Ms(a) memset(a,INF,sizeof(a))#define pi acos(-1.0)#define INF 0x3f3f3f3fconst double E=exp(1);const int maxn=1e3+10;using namespace std;int flag[maxn];int way[maxn][maxn];int dis[maxn];int point[maxn];int gg[maxn];int n,m;void Dijkstra(int v){ memset(flag,0,sizeof(flag)); int ans,x; gg[v]=point[v]; for(int i=0;i
                
                 dis[j]&&!flag[j]) { ans=dis[j]; x=j; } } flag[x]=1; for(int j=0;j
                 
                  way[x][j]+dis[x]) { dis[j]=way[x][j]+dis[x]; gg[j]=gg[x]+point[j]; } } for(int j=0;j
                  
                   >n>>m>>start>>end; int x,y,z; ms(gg); for(int i=0;i
                   
                    >point[i]; Ms(way); while(m--) { cin>>x>>y>>z; way[x][y]=way[y][x]=min(way[x][y],z); } Dijkstra(start); cout<
                    
                     <<" "<
                     
                      <

转载于:https://www.cnblogs.com/Friends-A/p/10324382.html

你可能感兴趣的文章