眼镜商城网站建设方案,济南抖音seo,网站建设案例单招网,门户网站开发哪家好题干#xff1a;
你来到一个迷宫前。该迷宫由若干个房间组成#xff0c;每个房间都有一个得分#xff0c;第一次进入这个房间#xff0c;你就可以得到这个分数。还有若干双向道路连结这些房间#xff0c;你沿着这些道路从一个房间走到另外一个房间需要一些时间。游戏规定…题干
你来到一个迷宫前。该迷宫由若干个房间组成每个房间都有一个得分第一次进入这个房间你就可以得到这个分数。还有若干双向道路连结这些房间你沿着这些道路从一个房间走到另外一个房间需要一些时间。游戏规定了你的起点和终点房间你首要目标是从起点尽快到达终点在满足首要目标的前提下使得你的得分总和尽可能大。现在问题来了给定房间、道路、分数、起点和终点等全部信息你能计算在尽快离开迷宫的前提下你的最大得分是多少么
Input
第一行4个整数n (500), m, start, end。n表示房间的个数房间编号从0到(n - 1)m表示道路数,任意两个房间之间最多只有一条道路start和end表示起点和终点房间的编号。 第二行包含n个空格分隔的正整数(不超过600)表示进入每个房间你的得分。 再接下来m行每行3个空格分隔的整数x, y, z (0 输入保证从start到end至少有一条路径。
Output
一行两个空格分隔的整数第一个表示你最少需要的时间第二个表示你在最少时间前提下可以获得的最大得分。
Sample Input
3 2 0 2
1 2 3
0 1 10
1 2 11
Sample Output
21 6
解题报告 此题采用邻接矩阵的方式储存图加一个维护ans数组。
AC代码
#includebits/stdc.husing namespace std;
const int MAX 505;
const int INF 0x3f3f3f3f;
int maze[505][505];
bool vis[MAX];
int dis[505],ans[505];
int val[505];
int n,m,st,ed;
struct Point {int pos,w;
};
void Dijkstra(int u,int v) {dis[u] 0;int all n, minw INF, minv;
// for(int i 0; in; i) dis[i] maze[u][i];ans[u] val[u];for(int k 1; kn; k) {minw INF;minv u;for(int i 0; in; i) {if(vis[i] ) continue;if(dis[i] minw) {minv i;minw dis[i];}}vis[minv] 1;if(minv v) break;for(int i 0; in; i) {if(vis[i] 0 maze[minv][i] !INF) {if(dis[i] dis[minv] maze[minv][i]) {dis[i] min(dis[i],dis[minv]maze[minv][i]);ans[i] ans[minv] val[i];}else if(dis[i]dis[minv]maze[minv][i]){ans[i]max(ans[i],ans[minv]val[i]);//若路径花费相等点权值取较大的。} }}}
// if(dis[v] !INF) printf(%d %d\n,dis[v],ans[v]);
// else printf(-1\n);}
void init() {memset(ans,0,sizeof(ans));memset(maze,INF,sizeof(maze));memset(dis,INF,sizeof(dis));memset(vis,0,sizeof(vis));memset(val,0,sizeof(val));
}
int main()
{int u,v,w;while(~scanf(%d%d%d%d,n,m,st,ed) ) {init();for(int i 0; in; i) {scanf(%d,val[i]);}while(m--) {scanf(%d%d%d,u,v,w);maze[u][v] maze[v][u] w;}Dijkstra (st,ed);}return 0 ;
}
//9:13
AC代码2用dfs路径还原还未看。。。。
#includestdio.h
#includealgorithm
#includestring.h
#includevector
using namespace std;
const int INF1e97;
const int maxm505;
int cost[maxm][maxm],dis[maxm],vis[maxm],w[maxm],s,e,n,m,ans0;
vectorintp[maxm];
void dijkstra();
void dfs(int k,int sum);
int main()
{int i,j,k,sum,x,y,z;scanf(%d%d%d%d,n,m,s,e);s;e;for(i1;in;i){for(j1;jn;j)cost[i][j]INF;}for(i1;in;i)scanf(%d,w[i]);for(i1;im;i){scanf(%d%d%d,x,y,z);cost[x1][y1]cost[y1][x1]z;}dijkstra();/*for(i1;in;i){for(j0;jp[i].size();j)printf(%d ,p[i][j]);printf(\n);}*/dfs(e,0);printf(%d %d\n,dis[e],ans);return 0;
}
void dijkstra()
{int i,j,k,u,v;memset(vis,0,sizeof(vis));for(i1;in;i)dis[i]INF;dis[s]0;while(true){int v-1;for(i1;in;i){if(!vis[i] (v-1 || dis[i]dis[v]))vi;}if(v-1)break;vis[v]1;for(i1;in;i){if(dis[i]dis[v]cost[v][i]){//printf(%d %d %d %d\n,v,i,dis[i],dis[v]cost[v][i]);p[i].clear();dis[i]dis[v]cost[v][i];p[i].push_back(v);}else if(dis[i]dis[v]cost[v][i])p[i].push_back(v);}}//for(i1;in;i)//printf(%d ,dis[i]);//printf(\n);
}
void dfs(int k,int sum)
{sumw[k];if(ks){ansmax(ans,sum);return;}for(int j0;jp[k].size();j)dfs(p[k][j],sum);
}总结 1.还是对Dijkstra算法不是很熟。。。小地方错一堆比如函数刚开始被注释掉的那个初始化显然不能加啊因为你这样让u到u的距离也成了INF了而且加上这句也不会有什么优化作用。。。如果非要加初始化的话那就把dis[u] 0放到他后面。 2. 当时在想 对于这个题 f(minv v) break; 这句话是不是不应该加 后来深刻理解了一下这句话的含义是因为第一步for筛选出了一个点minv并且把这个点当成完成点了第二个for在进行扩展所以既然这个点是完成点那么他的状态值都是完成值大家对这个值只能读不能写因此说是dp思想还是贪心思想来着。。。所以此时加上这句f(minv v) break;也是没错的。 3.看题解并没有写if(vis[i] 0 maze[minv][i] !INF)想想也是这一步只是优化了时间并不影响答案的正确性因为你有while(all--)所以函数还是有出口的。 4.对于这个题法1对maze初始化的时候不能 这样具体为什么自己思考一下。。。
