描述
Minya Konka
decided to go to Fuzhou to participate in the ACM regional contest at their own
expense.Through the efforts, they got a small amount of financial support from
their school, but the school could pay only one of those costs between two
stations for them.
From SWUST to Fujian Normal University which is the
contest organizer, there are a lot of transfer station and there are many
routes.For example, you can take the bus to Mianyang Railway Station (airport),
then take the train (plane) to Fuzhou,and then take a bus or taxi to the Fujian
Normal University.
The school could pay only one of those costs between two
stations for them, the others paid by the Minya Konka team members.They want to
know what is the minimum cost the need pay.Can you calculate the minimum
cost?
输入
There are
several test cases.
In each case,the first line has two integers
n(n<=100) and m(m<=500),it means there are n stations and m undirected
roads.
The next m lines, each line has 3 integers u,v,w,it means there is a
undirected road between u and v and it cost
w.(1<=u,v<=n,0<=w<=100)
The ID of SWUST is 1,and n is the ID of
Fujian Normal University.
输出
If they can not reach the destination output -1, otherwise output the minimum cost.
样例输入
5 5
1 2 7
1 3 3
3 4 3
2 5 3
4 5 3
样例输出
3
题目来源
题目的意思一开始有点不明白，经过贞贞的指导算有点明白了。
就是从起点到车站和车站到终点的这两段路是要自己付，车站跟车站之间是可以报销的，求最少要付多少钱。
至于为什么理解不了是因为没有考虑到起点和终点可以当一个车站。
用邻接矩阵做dijkstra一直过不了，后来用spfa才过的，不知道为什么，可能是重边没有处理好。
#include <stdio.h>#include <math.h>#include <queue>#include <vector>#include <iostream>#define inf 0x3f3f3f3f#define MAXN 105using
namespace
std;<br>
int
n,m;
bool
visited[MAXN];
struct
Node{
int
w;
int
to;
};vector<Node> vec[MAXN];<br>void
addedge(int
u, int
v, int
w){
Node no;
no.to=v;
no.w=w;
vec[u].push_back(no);
}void
spfa(int
begin ,int
dist[MAXN]){
for
(int
i=1; i<=n; i++){
dist[i]=inf;
visited[i]=false;
}
queue<Node> Q;
dist[begin] = 0;
visited[begin] = true;
Node now;
now.to=begin;
now.w=0;
Q.push(now);
while(!Q.empty()){
Node temp=Q.front();
Q.pop();
for(int
i=0; i<vec[temp.to].size(); i++){
Node t1=vec[temp.to][i];
int
v=temp.w + t1.w ;
if(v<dist[t1.to]){
dist[t1.to] =v;
t1.w=v;
Q.push(t1);
}
}
}
}int
main(int
argc, char
*argv[])
{ int
u,v,w;
int
dist1[MAXN];
int
dist2[MAXN];
while(scanf("%d %d",&n,&m)!=EOF){
for(int
i=1; i<=n; i++){
vec[i].clear();
}
for(int
i=1; i<=m; i++){
scanf("%d %d %d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
spfa(1,dist1);
spfa(n,dist2);
int
min=inf;
for(int
i=1; i<=n; i++){
int
size=vec[i].size();
for(int
j=0; j<size; j++){
int
to=vec[i][j].to;
if(dist1[i]!=inf && dist2[i]!=inf && dist1[i]+dist2[to]<min)
min=dist1[i]+dist2[to];
}
}
if(min==inf)
printf("-1\n");
else
printf("%d\n",min);
}
return
0;
} |