1思路： SPFA + 无向图邻接表
2分析：
1题目给定的n最大20000，m最大50000，分析复杂度后发现只有SPFA最靠谱。
2分析题目的样列可知，这一题是要用邻接矩阵来存储无向图，所以要注意无向图怎么存储在邻阶表中
2连接表的横列有N项，纵列也是N项。形成的N*N项每项都被称为边结点，每项都有纵横两个坐标，例如点（N,N-1），表示的就是从第N点向第N-1点有无路径。由于有E条边，自然有E条路径，但是由于无向=双向，所以要乘以2
3代码：
[cpp]
#include
#include
#include
#include
#include
using namespace std;
#define INF 0xFFFFFFF
#define MAXN 100010/*存储无向图的时候乘以2*/
int T , n , m , s , t;
int first[MAXN] , next[MAXN];
int star[MAXN] , end[MAXN] , value[MAXN];
int dis[MAXN];
queue
void init(){
while(!q.empty())
q.pop();
memset(first , -1 , sizeof(first));
memset(next , -1 , sizeof(next));
for(int i = 0 ; i < n ; i++){
if(i == s)
dis[i] = 0;
else
dis[i] = INF;
}
}
void SPFA(){
int vis[MAXN];
memset(vis , 0 , sizeof(vis));
q.push(s);
while(!q.empty()){
int tmp = q.front();
q.pop();
printf("%d\n" , first[tmp]);
for(int i = first[tmp] ; i !=-1 ; i = next[i]){
if(dis[end[i]] > dis[tmp] + value[i]){
dis[end[i]] = dis[tmp] + value[i];
if(!vis[end[i]]){
vis[end[i]] = 1;
q.push(end[i]);
}
}
}
}
}
int main(){
//freopen("input.txt" , "r" , stdin);
int cnt = 1;
scanf("%d" , &T);
while(T--){
scanf("%d%d%d%d" , &n , &m , &s , &t);
init();
for(int i = 0 ; i < m ; i++){
scanf("%d%d%d" , &star[i] , &end[i] , &value[i]);
star[i+m] = end[i];。/*这里要注意*/
end[i+m] = star[i]; /*这里要注意*/
value[i+m] = value[i];
next[i] = first[star[i]];
first[star[i]] = i;
next[i+m] = first[star[i+m]];
first[star[i+m]] = i+m;
}
SPFA();
if(!m || dis[t] == INF)
printf("Case #%d: unreachable\n" , cnt++);
else
printf("Case #%d: %d\n" , cnt++ , dis[t]);
}
return 0;
}