首页 > 代码库 > 51Nod 迷宫问题（最短路+权值）（模板）
51Nod 迷宫问题（最短路+权值）（模板）
你来到一个迷宫前。该迷宫由若干个房间组成，每个房间都有一个得分，第一次进入这个房间，你就可以得到这个分数。还有若干双向道路连结这些房间，你沿着这些道路从一个房间走到另外一个房间需要一些时间。游戏规定了你的起点和终点房间，你首要目标是从起点尽快到达终点，在满足首要目标的前提下，使得你的得分总和尽可能大。现在问题来了，给定房间、道路、分数、起点和终点等全部信息，你能计算在尽快离开迷宫的前提下，你的最大得分是多少么？
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 2 1 2 3 0 1 10 1 2 11
Output示例
21 6
注意vis[x]的标记，重点。
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <cstdlib> #include <iomanip> #include <cmath> #include <cassert> #include <ctime> #include <map> #include <set> using namespace std; #define lowbit(x) (x&(-x)) #define max(x,y) (x>y?x:y) #define min(x,y) (x<y?x:y) #define MAX 100000000000000000 #define MOD 1000000007 #define pi acos(-1.0) #define ei exp(1) #define PI 3.141592653589793238462 #define ios() ios::sync_with_stdio(false) #define INF 1044266558 #define mem(a) (memset(a,0,sizeof(a))) typedef long long ll; int val[505],dis[505],g[505][505]; int pos[505]; int vis[505]; int n,m,start,end; void init() { memset(g,62,sizeof(g)); memset(pos,0,sizeof(pos)); memset(vis,0,sizeof(vis)); } void dij(int x,int y) { for(int i=0;i<n;i++) { dis[i]=g[x][i]; } dis[x]=0; pos[x]=val[x]; for(int i=0;i<n;i++) { int minn=INF; int v=x; for(int j=0;j<n;j++) { if(!vis[j] && minn>dis[j]) { minn=dis[j]; v=j; } } vis[v]=1; for(int j=0;j<n;j++) { if(dis[j]>dis[v]+g[v][j]) { dis[j]=dis[v]+g[v][j]; pos[j]=pos[v]+val[j]; } else if(dis[j]==dis[v]+g[v][j]) { pos[j]=max(pos[j],val[j]+pos[v]); } } } printf("%d %d\n",dis[y],pos[y]); } int main() { int x,y,w; while(scanf("%d%d%d%d",&n,&m,&start,&end)!=EOF) { memset(g,62,sizeof(g)); for(int i=0;i<n;i++) scanf("%d",&val[i]); for(int i=0;i<m;i++) { scanf("%d%d%d",&x,&y,&w); g[x][y]=g[y][x]=w; } dij(start,end); } return 0; }
51Nod 迷宫问题（最短路+权值）（模板）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。