基本知識
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]<<" ";
}
總結
今天是學習圖論第一天…加油，道阻且長…
![線程同步，可重入鎖，synchronized[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)