今天什么都没有学（x），做了一组十题的练习，英文果然是个使人惆怅的东西。
练习：https://vjudge.net/contest/209626#overview
A题water，B题大家都没写还以为是个可怕的大卡车，没想到是个dijkstra，和PAT甲级里的1003emergency相似度极高，C题在学校oj上做过，D题得用KMP，强行学了一波OTZ，E题water，H题STL map。
贴一下B题。
Your boss has hired you to drive a big truck, transporting items between two locations in a city. You’re given a description of the city, with locations of interest and the lengths of roads between them. Your boss requires that you take a shortest path between the starting and ending location, and she’ll check your odometer when you’re done to make sure you didn’t take any unnecessary side trips. However, your friends know you have plenty of unused space in the truck, and they have asked you to stop by several locations in town, to pick up items for them. You’re happy to do this for them. You may not be able to visit every location to pick up everything your friends want, but you’d like to pick up as many items as possible on your trip, as long as it doesn’t make the path any longer than necessary.
The two graphs above show examples of what the city may look like, with nodes representing locations, edges representing roads and dots inside the nodes representing items your friends have asked you to pick up. Driving through a location allows you to pick up all the items there; it’s a big truck, with no limit on the items it can carry. In the graph on the left, for example, you have to drive the big truck from location $1$ to location $6$. If you follow the path $1 \rightarrow 2 \rightarrow 3 \rightarrow 6$, the length is $9$, and you’ll get to pick up $4$ items. Of course, it would be better to drive $1 \rightarrow 4 \rightarrow 5 \rightarrow 6$; that’s still a length of $9$, but going this way instead lets you pick up an additional item. Driving $1 \rightarrow 4 \rightarrow 3 \rightarrow 6$ would let you pick up even more items, but it would make your trip longer, so you can’t go this way.
Input
The first line of input contains an integer, $n$ ($2 \leq n \leq 100$), giving the number of locations in the city. Locations are numbered from $1$ to $n$, with location $1$ being the starting location and $n$ being the destination. The next input line gives a sequence of $n$ integers, $t_1 \ldots t_ n$, where each $t_ i$ indicates the number of items your friends have asked you to pick up from location $i$. All the $t_ i$ values are between $0$ and $100$, inclusive. The next input line contains a non-negative integer, $m$, giving the number of roads in the city. Each of the following $m$ lines is a description of a road, given as three integers, $a \: b \: d$. This indicates that there is a road of length $d$ between location $a$ and location $b$. The values of $a$ and $b$ are in the range $1 \ldots n$, and the value of $d$ is between $1$ and $100$, inclusive. All roads can be traversed in either direction, there is at most one road between any two locations, and no road starts and ends at the same location.
Output
If it’s not possible to travel from location $1$ to location $n$, just output out the word “impossible”. Otherwise, output the length of a shortest path from location $1$ to location $n$, followed by the maximum number of items you can pick up along the way.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 |
9 5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
9 |
12 7 |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 |
impossible |
代码如下(悄咪咪改了一下之前写的emergency的代码)↓
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxv = 1010;
const int inf = 100000000000;
int mp[maxv][maxv],weight[maxv];//邻接矩阵mp记录无向图，weight记录点权
int m,n,st,ed,num[maxv],w[maxv],d[maxv];//n是地点个数，m是边数，st是起点，ed是终点，num是最短路径条数，w是最大点权和，d是最短距离
bool vis[maxv]={false};//标记某点是否被访问
void dijkstra(int s)
{
fill(d,d+maxv,inf);
memset(num,0,sizeof(num));
memset(w,0,sizeof(w));
d[s]=0;
w[s]=weight[s];
num[s]=1;
for(int i = 0;i<n;i++)
{
int u = -1,min=inf;//u让d[u]最小，min存最小的d[u]
for(int j =0;j<n;j++)//找没有访问的点里d[]最小的
{
if(vis[j]==false&&d[j]<min)
{
u=j;
min=d[j];
}
}
if(u==-1) return;//找不到小于inf的d[u]，剩下的点和起点不连通
vis[u]=true;//u被访问
for(int v=0;v<n;v++)
{
if(vis[v]==false&&mp[u][v]!=inf)//若v未被访问过且u为中介点可以松弛d[v]
{
if(d[u]+mp[u][v]<d[v])
{
d[v]=mp[u][v]+d[u];
w[v]=w[u]+weight[v];
num[v]=num[u];
}
else if(d[u]+mp[u][v]==d[v])//找到了一条相同长度的路径
{
if(w[u]+weight[v]>w[v])//若u为中介可以使点权和变大
w[v]=w[u]+weight[v];
num[v]+=num[u];//更新最短路径条数
}
}
}
}
}
int main()
{
scanf("%d",&n);
for(int i =0;i<n;i++)
{
scanf("%d",&weight[i]);
}
ed=n-1;//因为是从0开始读的所以终点要n-1
int u,v;
fill(mp[0],mp[0]+maxv*maxv,inf);//初始化邻接矩阵
scanf("%d",&m);
for(int i =0;i<m;i++)
{
scanf("%d%d",&u,&v);
scanf("%d",&mp[u-1][v-1]);//因为编号从0开始，所以要把题目给的-1
mp[v-1][u-1]=mp[u-1][v-1];
}
dijkstra(0);//从0开始的dijkstra入口
if(w[ed]!=0)//最大点权和不是0，意味着可以走到终点
printf("%d %d\n",d[ed],w[ed]);
else
printf("impossible");
return 0;
}