題目描述：給出列車的行駛路徑，和每個路徑是硬座還是軟臥，並且給出硬座和軟臥的不舒適度，求從起點到終點最小的不舒適度。
思路：首先分別求出硬座和軟臥從起點到終點的距離，最後比較不舒適度，當然這題得建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 ++)
{
add(q[i-1],q[i],j);
}
//for(int i = 0 ;i < l ;i ++)cout <<q[ i ]<<endl;
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 <<step1 * S<<" "<<step2 * D<<endl;
if(step1 == -1 && step2 == -1)//無法到達
cout << -1<<endl;
else
{
if(step1 == -1)
cout <<step2 * D<<endl;
else if(step2 == -1)
cout <<step1 * S<<endl;
else
cout << min(step1 * S,step2 * D)<<endl;
}
}
return 0;
}
#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 ++)
{
add(q[i-1],q[i],j);
}
//for(int i = 0 ;i < l ;i ++)cout <<q[ i ]<<endl;
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 <<step1 * S<<" "<<step2 * D<<endl;
if(step1 == -1 && step2 == -1)//無法到達
cout << -1<<endl;
else
{
if(step1 == -1)
cout <<step2 * D<<endl;
else if(step2 == -1)
cout <<step1 * S<<endl;
else
cout << min(step1 * S,step2 * D)<<endl;
}
}
return 0;
}
