HDU 4522 最短路

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

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

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

[cpp]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#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<pair<int,int> >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();
            vector<int>q;
            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 ++)
                {
                    a

补充：软件开发 , C++ ,