HDU 4522 最短路 - c++编程基础

题目描述：给出列车的行驶路径，和每个路径是硬座还是软卧，并且给出硬座和软卧的不舒适度，求从起点到终点最小的不舒适度。

思路：首先分别求出硬座和软卧从起点到终点的距离，最后比较不舒适度，当然这题得建2个图，一个是硬座的路径，一个是软卧的路径，得注意的是，当K= 1时，是硬座软卧都有，所以两边都得加进去。

其他的没什么，就是最基础的最短路。比赛的时候没有好好看题=。=

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define PI acos(-1.0)
#define Max 2005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;

int head[2][500];
struct kdq
{
int s,e,next;
} edge[2][2000];
int num[2] ;
bool vis[2][500];
void add(int s,int e,int k )
{
edge[k][num[k]].e = e;
edge[k][num[k]].next = head[k][s];
head[k][s] = num[k] ++;
}
void init()
{
mem(head,-1);
mem(vis,0);
num[0] = num[1] = 0 ;
}
char a[10005];
int StringToInt(string x)
{
int l = x.size();
int num = 0;
for (int i = l - 1 ; i >= 0 ; i --)
{
num += (x[i] - '0') * pow(10.0,(double)(l - i - 1));
}
return num ;
}
int dis[2][500];
int n ;
#define x first
#define y second
int spfa(int s,int e,int k)
{
for (int i = 0 ;i <= n ; i ++)dis[k][i] = inf;
dis[k][s] = 0;
vis[k][s] = 1;
queue >q;
q.push(mp(s,0));
while(!q.empty())
{
int temp = q.front().x;
int step = q.front().y;
q.pop();
vis[k][temp] = 0;
if(temp == e)
return step ;
for (int i = head[k][temp] ; i != -1 ;i = edge[k][i].next)
{
int tt = edge[k][i].e;
if(dis[k][tt] > dis[k][temp] + 1)
{
dis[k][tt] = dis[k][temp] + 1;
if(!vis[k][tt])
{
vis[k][tt] = 1;
q.push(mp(tt,step + 1));
}
}
}
}
return -1;
}
int main()
{
int T;
cin >> T;
while ( T -- )
{
int m ;
cin >> n >> m;
init();
while ( m -- )
{
scanf("%s",a);
int k ;
cin >> k;
int l = strlen(a);
string x ;
x.clear();
vectorq;
for (int i = 0 ; i < l ; i ++)
{
if(a[i] == '+')
{
q.push_back(StringToInt(x));
x.clear();
}
else
x += a[i];
}
q.push_back(StringToInt(x));
l = q.size();
for (int j = 0 ; j <= k ; j ++)//当k = 1 时，硬座和软卧都要加入该路径。
for (int i = 1 ; i < l ; i ++)
{
add(q[i-1],q[i],j);
}
//for(int i = 0 ;i < l ;i ++)cout < q.clear();
}
int s,e,S,D;
cin >> S>>D>>s>>e;
int step1 = spfa(s,e,0);//硬座的距离
int step2 = spfa(s,e,1);//软卧的距离
//cout < if(step1 == -1 && step2 == -1)//无法到达
cout << -1< else
{
if(step1 == -1)
cout < else if(step2 == -1)
cout < else
cout << min(step1 * S,step2 * D)< }
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define PI acos(-1.0)
#define Max 2005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,si

HDU 4522 最短路 (一)