csu 十月月赛最短路+最小费用

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。

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 using namespace std;
 5 typedef long long LL;
 6 const int maxn=1000+5;
 7 const long long INF=1e+9;
 8 bool v[maxn];
 9 int d[maxn];
10 int cost[maxn];
11 int girl[maxn];
12 int w[maxn][maxn];
13 int p[maxn][maxn];
14 int main()
15 {
16     int n,m;
17     while(~scanf("%d%d",&n,&m)&&n&&m)
18     {
19         for(int i=1;i<=n;i++)
20          for(int j=1;j<=n;j++)
21          {
22              w[i][j]=INF;//路径长度
23              p[i][j]=0;
24          }
25         for(int i=1;i<=n;i++)
26         {
27             scanf("%d",&girl[i]);
28         }
29         for(int i=0;i<m;i++)
30         {
31             int a,b,c;
32             scanf("%d%d%d",&a,&b,&c);
33             if (w[a][b]>c) {w[a][b]=c,w[b][a]=c;p[a][b]=girl[b];p[b][a]=girl[a];}
34         }
35         int a,b;
36         //scanf("%d%d",&a,&b);
37         a=1;b=n;
38         for(int i=1;i<=n;i++)
39         if (i==a) v[i]=1;else v[i]=0;
40         memset(v,0,sizeof(v));
41         for(int i=1;i<=n;i++)
42         d[i]=INF,cost[i]=0;
43 
44         d[a]=0;
45         cost[a]=girl[1];
46         for(int i=1;i<=n;i++)
47         {
48             LL m1=INF;
49             //LL m2=INF;
50             int x;
51             for(int j=1;j<=n;j++)
52             if (!v[j])
53             {
54                 if (d[j]<m1) m1=d[j],x=j;
55             }
56             v[x]=1;
57             for(int j=1;j<=n;j++)
58             {
59                 if(d[j]>d[x]+w[x][j]) d[j]=d[x]+w[x][j], cost[j]=cost[x]+p[x][j];
60                 else if (d[j]==d[x]+w[x][j] && cost[j]<cost[x]+p[x][j]) cost[j]=cost[x]+p[x][j];
61             }
62         }
63 
64         if (d[n]==INF)printf("-1
");else
65         printf("%d
",cost[b]);
66     }
67     return 0;
68 
69 }

View Code

//模板题，注意判断条件

csu 十月月赛 最短路+最小费用

Description

Input

Output

csu 十月月赛最短路+最小费用