基本知识
Dijkstra基本思想
拓扑排序思维视频讲解
848：有向图的拓扑排序
题目链接
题解：
#include<bits/stdc++.h>using namespace std;const int N=100010;int n,m;int h[N],e[N],ne[N],idx;int d[N];//d[j]代表点j的入度数量 int q[N];//用数组模拟队列，避免queue中的pop，保留元素 void add(int a,int b)//建立邻接表存储图 {e[idx]=b;ne[idx]=h[a];h[a]=idx++;}bool topsort()//模拟队列，判断是否为有向无环图 {int hh=0,tt=-1;//队头，队尾 for(int i=1;i<=n;i++){if(!d[i]) q[ ++tt ] = i ;//将入度为0的点入队 }while(tt>=hh){int t=q[hh++];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(--d[j]==0){q[++tt]=j;}}}return tt==n-1;//表示n个点都入队了，则为有向无环图，即拓扑图 }int main(){cin>>n>>m;memset(h,-1,sizeof h);for(int i=0;i<m;i++){int a,b;cin>>a>>b;add(a,b);d[b]++;}if(topsort()){for(int i=0;i<n;i++) cout<<q[i]<<" ";}else{cout<<-1;}return 0;}
849：Dijkstra求最短路I – 朴素实现
题目
题解：
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=510;int dis[N],pic[N][N];bool st[N];//标记该点的最短距离是否已经被确定 //未优化版本 int main(){int n,m;cin>>n>>m;memset(pic,0x3f,sizeof(pic));for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;pic[u][v]=min(pic[u][v],w);//对于重边的处理 }memset(dis,0x3f,sizeof(dis));dis[1]=0;//到自身距离为0 for(int i=1;i<=n;i++)//有n个点所以n次迭代 {int t=-1;//t用于储存当前被访问的点 for(int j=1;j<=n;j++){//改不走寻找还未确定的最短路的点当中 路径最短的点 if(!st[j]&&(t==-1||dis[t]>dis[j]))t=j;}st[t]=1;//到t点的最短路已经确定 for(int j=1;j<=n;j++)//依次更新每个点到相邻的点的最短路<--新确定的最短路的点会影响未确定的点 dis[j]=min(dis[j],dis[t]+pic[t][j]);}if(dis[n]==0x3f3f3f3f) cout<<-1<<endl;//到n点没有路径 else cout<<dis[n];return 0;}
850. Dijkstra求最短路 II – 优化
题目
题解：面对数据较大情况（点的数量超过1e5，不再适合用二维数组存，二维数组开到1e5会爆），使用优先队列优化，使用临界矩阵存图（适用于稀疏图）
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e6+10;typedef pair<int, int> pii;int dis[N];int h[N],e[N],ne[N],idx;int w[N];//存权重 bool st[N];//标记该点的最短距离是否已经被确定//优化版本，用邻接矩阵存图 void add(int a,int b,int c){e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;}int main(){int n,m;cin>>n>>m;memset(h,-1,sizeof(h));for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w); }memset(dis,0x3f,sizeof(dis));dis[1]=0;//到自身距离为0 priority_queue<pii, vector<pii>, greater<pii> >heap;heap.push({0,1});//先存距离，再存点while(heap.size()){auto t=heap.top();heap.pop();int ver=t.second,distance= t.first;if(st[ver]) continue;st[ver]=true;for(int i=h[ver];i!=-1;i=ne[i]){int j=e[i];if(dis[j]>dis[ver]+w[i]){dis[j]=dis[ver]+w[i];heap.push({dis[j],j});}}}if(dis[n]==0x3f3f3f3f) cout<<-1<<endl;//到n点没有路径 else cout<<dis[n];return 0;}
P4779 【模板】单源最短路径（标准版）
题目
上述Dijkstra都是寻找从1到n的最短路，本题寻找从第s个点出发，到每个点的距离
题解：
#include<bits/stdc++.h>#define pii pair<int, int>using namespace std;typedef long long ll;const int inf=0x3f3f3f3f;const int N=1e5+10;int n,m,s;ll dis[N];bool vis[N];struct node{int to,len;};vector<node> f[N];void diji(int t){memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));dis[t]=0;//注意初始化priority_queue<pii, vector<pii>, greater<pii> >q;q.push(pii(0,t));//从第t个点开始的精髓于此while(!q.empty()){pii p=q.top();q.pop();int tt=p.second;if(vis[tt]) continue;vis[tt]=true;for (int i=0;i<f[tt].size();i++){node a=f[tt][i];if(dis[a.to]>dis[tt]+a.len){dis[a.to]=dis[tt]+a.len;q.push(pii(dis[a.to],a.to));}}}}int main(){cin>>n>>m>>s;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;f[u].push_back({v,w});}diji(s);for(int i=1;i<=n;i++) cout<<dis[i]<<" ";}
总结
今天是学习图论第一天…加油，道阻且长…
