首页 > 代码库 > CSU 1312 CX and girls (最短路)
CSU 1312 CX and girls (最短路)
1321: CX and girls
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 432 Solved: 124
[Submit][Status][Web Board]
Description
CX是要赶去上课，为了不迟到必须要以最短的路径到达教室，同时CX希望经过的路上能看到的学妹越多越好。现在把地图抽象成一个无向图，CX从1点出发，教室在N号点，告诉每个点上学妹的数量，每条边的长度。请你求出CX以最短路径赶到教室最多能看到多少学妹。
Input
多组输入数据(最多20组)，输入到文件结束。
每组数据第一行两个正整数N,M其中N代表点的个数(2<=N<=1000),M代表边的个数(1<=M<=10000)。
接下来一行N个数，代表着1~N每个点上学妹的个数，(0<=Ni<=50)。 接下来M行，每行三个数A B C(1<=A,B<=N,0<c<=100)代表A,B间有边，长度为C。(可能存在重边)
Output
输出CX以最短距离从1到n的情况下能看到的最多学妹数量，若从点1无法到达点N输出-1。
Sample Input
4 41 2 3 41 2 11 3 12 4 23 4 2Sample Output
8HINT
CSU_ZZY
Source
CSU Monthly 2013 Oct.
这里使用最短路，只是多了一个权值，找到最短路，输出妹子的数量，如果有多个最短路，输出妹子最多的那一个
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<stdlib.h> 5 #include<algorithm> 6 using namespace std; 7 const int INF=0x3f3f3f3f; 8 const int MAXN=1000+20; 9 int w[MAXN][MAXN],dis[MAXN],num[MAXN],a[MAXN],vis[MAXN];10 int n,m;11 void dijkstra()12 {13 memset(vis,0,sizeof(vis));14 for(int i=1;i<=n;i++)15 dis[i]=INF;16 17 dis[1]=0;18 a[1]=num[1];19 for(int i=1;i<=n;i++)20 {21 int x,temp=INF;22 for(int j=1;j<=n;j++)23 {24 if(!vis[j]&&dis[j]<=temp)25 {26 x=j;27 temp=dis[j];28 }29 }30 vis[x]=1;31 for(int k=1;k<=n;k++)32 {33 if(dis[k]>dis[x]+w[x][k])34 {35 dis[k]=dis[x]+w[x][k];36 a[k]=a[x]+num[k];37 }38 else if(dis[k]==dis[x]+w[x][k]&&a[k]<a[x]+num[k])39 a[k]=a[x]+num[k];40 }41 }42 }43 int main()44 {45 //freopen("in.txt","r",stdin);46 while(scanf("%d %d",&n,&m)!=EOF)47 {48 for(int i=1;i<=n;i++)49 scanf("%d",&num[i]);50 51 for(int i=1;i<=n;i++)52 for(int j=1;j<=n;j++)53 w[i][j]=INF;54 55 for(int i=1;i<=m;i++)56 {57 int star,en,val;58 scanf("%d %d %d",&star,&en,&val);59 if(val<w[star][en])60 w[star][en]=w[en][star]=val;61 }62 63 dijkstra();64 65 if(dis[n]==INF)66 printf("-1\n");67 else68 printf("%d\n",a[n]);69 }70 return 0;71 }
CSU 1312 CX and girls (最短路)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。