一般形式的用邻接矩阵来实现dijkstra效率比较低，我这里直接记录的是用邻接表的方法以及用优先队列加以应用。
首先解释什么是dijkstra算法
dijkstra算法
dijkstra算法适用于求单源最短路，即可以求出起点到其余各点之间的最短路。它的算法实现是一个不断更新的过程。
举一个最简单的例子，假设有这么一个图
，红色表示权值，黑色表示4个点以及路径，我们假设起点为1，用d[i]来表示1到i的最短路，那么在第一轮的时候，d[2]=1,d[3]=1,d[4]=5，再下一轮的时候会对这个情况进行更新，结果为d[2]=1,d[3]=1,d[4]=4,以此类推，会一直更新到d[2]=1,d[3]=1,d[4]=3为止，所以我认为该算法是一个不断更新的过程。
邻接表表示法
邻接表表示法我们使用vector以及pair两种工具，可以极大的节省空间以及算法实现中遍历搜索的时间，举一个例子
该图的邻接表表示为
，具体实现可以看代码
解题思路大概就是把默认指向的轨道的权值设为0，需要开关的轨道权值设为1。
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <algorithm> 5 #include <queue> 6 #include <stack> 7 #include <stdio.h> 8 #include <cmath> 9 #include <string.h> 10 using namespace std; 11 #define ll long long 12 static const int WHITE=0;//未选 13 static const int GRAY=1;//备选 14 static const int BLACK=2;//已选 15 static const int INFTY=(1<<20); 16 int N,A,B; 17 vector<pair<int,int> > adj[105];//加权图的邻接表表示法 18 void dijkstra() 19 { 20 priority_queue<pair<int,int> > que;//用优先队列，first表示路径成本，second表示路口 21 int color[105],d[105]; 22 for(int i=1;i<=N;i++)//初始化 23 { 24 d[i]=INFTY; 25 color[i]=WHITE; 26 } 27 d[A]=0;//设置起点 28 que.push(make_pair(0,A)); 29 color[A]=GRAY; 30 while (!que.empty()) 31 { 32 pair<int,int> f=que.top(); 33 que.pop(); 34 int u=f.second; 35 color[u]=BLACK; 36 if(d[u]<f.first*(-1))//取出最小值，若不是最短路则忽略 37 continue; 38 for(int j=0;j<adj[u].size();j++)//更新最短路 39 { 40 int v=adj[u][j].first; 41 if(color[v]==BLACK) 42 continue; 43 if(d[v]>d[u]+adj[u][j].second) 44 { 45 d[v]=d[u]+adj[u][j].second; 46 que.push(make_pair(d[v]*(-1),v));//因为优先队列默认优先较大值，所以乘以-1 47 color[v]=GRAY; 48 } 49 } 50 } 51 if(d[B]==INFTY) 52 cout<<"-1"<<endl; 53 else 54 { 55 cout<<d[B]<<endl; 56 } 57 58 } 59 int main() 60 { 61 //freopen("C:\Users\16599\Desktop\in.txt","r",stdin); 62 scanf("%d%d%d",&N,&A,&B); 63 for(int i=1;i<=N;i++) 64 { 65 int K,a; 66 scanf("%d",&K); 67 if(K!=0)//注意k可能为0 68 { 69 scanf("%d",&a); 70 adj[i].push_back(make_pair(a,0));//表示第i个路口默认通向第a个路口，权值为0 71 } 72 for(int j=2;j<=K;j++) 73 { 74 scanf("%d",&a); 75 adj[i].push_back(make_pair(a,1));//表示第i个路口通向第a个路口需要按开关，权值为1 76 } 77 } 78 dijkstra(); 79 return 0; 80 }
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <algorithm> 5 #include <queue> 6 #include <stack> 7 #include <stdio.h> 8 #include <cmath> 9 #include <string.h> 10 using namespace std; 11 #define ll long long 12 static const int WHITE=0; 13 static const int GRAY=1; 14 static const int BLACK=2; 15 static const int INFTY=(1<<20); 16 int T,C,TS,TE; 17 vector<pair<int,int> > adj[2505]; 18 void dijkstra() 19 { 20 priority_queue<pair<int,int> > que; 21 int color[2505],d[2505]; 22 for(int i=1;i<=T;i++) 23 { 24 d[i]=INFTY; 25 color[i]=WHITE; 26 } 27 d[TS]=0; 28 que.push(make_pair(0,TS)); 29 color[TS]=GRAY; 30 while (!que.empty()) 31 { 32 pair<int,int> f=que.top(); 33 que.pop(); 34 int u=f.second; 35 color[u]=BLACK; 36 if(d[u]<f.first*(-1)) 37 continue; 38 for(int j=0;j<adj[u].size();j++) 39 { 40 int v=adj[u][j].first; 41 if(color[v]==BLACK) 42 continue; 43 if(d[v]>d[u]+adj[u][j].second) 44 { 45 d[v]=d[u]+adj[u][j].second; 46 que.push(make_pair(d[v]*(-1),v)); 47 color[v]=GRAY; 48 } 49 } 50 } 51 cout<<d[TE]<<endl; 52 } 53 int main() 54 { 55 //freopen("C:\Users\16599\Desktop\in.txt","r",stdin); 56 scanf("%d%d%d%d",&T,&C,&TS,&TE); 57 while(C--) 58 { 59 int rs,re,ci; 60 scanf("%d%d%d",&rs,&re,&ci); 61 adj[rs].push_back(make_pair(re,ci)); 62 adj[re].push_back(make_pair(rs,ci)); 63 } 64 dijkstra(); 65 return 0; 66 }