kuangbin專題題目一
本文是kuangbin專題的最短路練習(xí)題解，題解可能寫的不是很清晰，不過不重要，代碼還是很容易理解的。
做題順序
Dijkstra 1 7 4 10 3 2 16
spfa 14 12 13 5 15 18
floyd 8 6 9
附上題目鏈接
kuangbin專題鏈接
1 Til the Cows Come Home

#include<iostream> #include<map> #include<queue> #include<algorithm> #include<cstring> #define inf 0x3f3f3f3f using namespace std; const int maxn = 5005; struct node {int v,next,w; }edge[maxn]; int cnt; bool vis[maxn]; int dis[maxn],head[maxn]; int done[maxn]; int pre[maxn]; struct s_node{int x,x_dis;s_node(int b,int c){x=b;x_dis=c;}bool operator<(const s_node &a) const{return x_dis > a.x_dis;} }; void add(int u,int v,int w)//起點，終點，距離,鏈式前向星建圖 {edge[cnt].w=w;edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++; } void dijkstra(int n) {int s=1;priority_queue<s_node>Q;memset(dis,inf,sizeof dis);memset(done,0,sizeof done);Q.push(s_node(s,dis[s]));dis[s]=0;while(!Q.empty()){s_node u = Q.top();Q.pop();if(done[u.x]) continue;//丟棄已經(jīng)找到最短路徑的結(jié)點done[u.x]=true;for(int i=head[u.x];~i;i=edge[i].next){int v=edge[i].v;if(dis[v]>dis[u.x]+edge[i].w)//松弛操作{dis[v]=dis[u.x]+edge[i].w;Q.push(s_node(v,dis[v]));//把新遍歷的點加到堆中pre[v]=u.x;}}}cout<<dis[n]<<endl;//print_pre(s,n); } int main() {int n,m,u,v,w;cin>>m>>n;memset(head,-1,sizeof(head));for(int i = 0;i<m;i++){cin>>u>>v>>w;add(u,v,w);add(v,u,w);}dijkstra(n);//for(int i=1;i<=n;i++) cout<<dis[i]<<endl;return 0; } /*測試數(shù)據(jù)6 91 2 11 3 122 3 92 4 33 5 54 3 44 5 134 6 155 6 4*/

7 MPI Maelstrom

#include<iostream> #include<cstring> #include<map> #include<queue> #define MAX 105 using namespace std; int inf=1<<30; int N,T,S,D; int mp[MAX][MAX]; int dis[MAX]; int vis[MAX]; int turn(string s) {int f=0;for(int i=0;i<s.size();i++){int t=s[i]-'0';f=f*10+t;}return f; } void input() {cin>>N;S=1;D=N;for(int i=1;i<=N;i++){for(int j=1;j<=N;j++){if(i==j)mp[i][j]=0;elsemp[i][j]=inf;}}for(int i=2;i<=N;i++){for(int j=1;j<i;j++){string str;cin>>str;int c;if(str=="x"){continue;}else{c=turn(str);if(mp[i][j]!=0&&mp[i][j]!=inf){mp[i][j]=min(mp[i][j],c);mp[j][i]=mp[i][j];}else{mp[i][j]=c;mp[j][i]=c;}}}}for(int i=1;i<=N;i++){dis[i]=inf;vis[i]=0;}vis[S]=1;dis[S]=0; } void Dijkstra() {for(int i=1;i<=N;i++){int min_dis=inf;int min_sign=S;for(int j=1;j<=N;j++){if(dis[j]<min_dis&&!vis[j]){min_sign=j;min_dis=dis[j];}}vis[min_sign]=1;for(int j=1;j<=N;j++){if(!vis[j]){if(dis[j]>mp[j][min_sign]+dis[min_sign]){dis[j]=mp[j][min_sign]+dis[min_sign];}}}} } int main() {input();Dijkstra();int min_ans=-1;for(int i=2;i<=N;i++)min_ans=max(min_ans,dis[i]);cout<<min_ans<<endl; }/* 5 8 2 1 50 3 1 30 3 2 5 4 1 100 4 2 20 4 3 50 5 1 10 5 4 10 */

4 Silver Cow Party

#include<iostream> #include<cstring> #include<queue> #include<map> #define MAX 1005 using namespace std; int inf = 1<<30; int mp[MAX][MAX]; int N,X,M; int vis[MAX]; int dis1[MAX]; int dis2[MAX]; void judge() {cin>>N>>M>>X;for(int i=1;i<=N;i++){for(int j=1;j<=N;j++){mp[i][j]=inf;mp[j][i]=inf;}dis1[i]=inf;dis2[i]=inf;vis[i]=0;} } void input() {for(int i=0;i<M;i++){int a,b,c;cin>>a>>b>>c;if(mp[a][b]!=0&&mp[a][b]!=inf){mp[a][b]=min(mp[a][b],c);}elsemp[a][b]=c;} } void Dijkstra() {int min_sign=X;int min_dis=inf;vis[X]=1;dis1[X]=0;for(int i=1;i<=N;i++){min_sign=X;min_dis=inf;for(int j=1;j<=N;j++){if(!vis[j]&&dis1[j]<min_dis){min_sign=j;min_dis=dis1[j];}}vis[min_sign]=1;for(int j=1;j<=N;j++){if(!vis[j]){if(dis1[j]>dis1[min_sign]+mp[min_sign][j]){dis1[j]=dis1[min_sign]+mp[min_sign][j];}}}}memset(vis,0,sizeof vis);vis[X]=1;dis2[X]=0;for(int i=1;i<=N;i++){min_sign=X;min_dis=inf;for(int j=1;j<=N;j++){if(!vis[j]&&dis2[j]<min_dis){min_sign=j;min_dis=dis2[j];}}vis[min_sign]=1;for(int j=1;j<=N;j++){if(!vis[j]){if(dis2[j]>dis2[min_sign]+mp[j][min_sign]){dis2[j]=dis2[min_sign]+mp[j][min_sign];}}}} } int main() {judge();input();Dijkstra();int mans=-1;/*for(int i=1;i<=N;i++)cout<<dis1[i]<<" ";cout<<endl;for(int i=1;i<=N;i++)cout<<dis2[i]<<" ";cout<<endl; */for(int i=1;i<=N;i++){mans=max(mans,dis1[i]+dis2[i]);}cout<<mans<<endl; }

10 Invitation Cards

#include<iostream> #include<queue> #include<map> #include<cstring> #include<cstdio> #include<vector> using namespace std; const long long inf=0x3f3f3f3f3f3f3f3f; const int MAX=1000000+10; int N,M,T; struct Edge{int v;int w;int next; }fp[MAX]; int cnt; int head[MAX]; long long dis[MAX]; int temp[MAX][3]; int vis[MAX]; inline int read() {char ch = getchar();int x = 0, f = 1;while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}while('0' <= ch && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; }inline void write(int x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0'); } void add(int a,int b,int c) {fp[cnt].v=b;fp[cnt].w=c;fp[cnt].next=head[a];head[a]=cnt++; } void op1() {cnt=0;memset(vis,0,sizeof(vis));memset(head,-1,sizeof(head));for(int i=1;i<=N;i++){dis[i]=inf;vis[i]=0;head[i]=-1;} } struct cmp{bool operator() (const int a,const int b){return dis[a]>dis[b];}}; long long Dijkstra() {priority_queue<int,vector<int>,cmp>q;q.push(1);dis[1]=0;while(!q.empty()){int r=q.top();q.pop();//if(vis[r]) continue;vis[r]=1;for(int i=head[r];~i;i=fp[i].next){int v=fp[i].v;int w=fp[i].w;if(!vis[v]&&dis[v]>dis[r]+w){dis[v]=dis[r]+w;q.push(v);}}}long long ans=0;for(int i=1;i<=N;i++)ans+=dis[i];return ans; } int main() {T=read();while(T--){//cin>>N>>M;N=read();M=read();long long ans=0;op1();for(int i=0;i<M;i++){//scanf("%d%d%d",&temp[i][0],&temp[i][1],&temp[i][2]);//cin>>temp[i][0]>>temp[i][1]>>temp[i][2];temp[i][0]=read();temp[i][1]=read();temp[i][2]=read();add(temp[i][0],temp[i][1],temp[i][2]);}ans+=Dijkstra();op1();for(int i=0;i<M;i++){add(temp[i][1],temp[i][0],temp[i][2]);}ans+=Dijkstra();//write(ans);cout<<ans<<endl;}return 0; }

8 Cow Contest

#include<iostream> #include<map> #include<queue> #include<algorithm> #include<cstring> #define inf 0x3f3f3f3f using namespace std; const int maxn = 205; int mp[maxn][maxn]; int n,m; void floyd() {for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(mp[i][k]&&mp[k][j]) mp[i][j]=1;}}}int ans=0;for(int i=1;i<=n;i++){int c=0;for(int j=1;j<=n;j++){if(mp[i][j]||mp[j][i]) c++;}if(c==n-1) ans++;}cout<<ans<<endl; } int main() {cin>>n>>m;for(int i=0;i<m;i++){int u,v;cin>>u>>v;mp[u][v]=1;}floyd(); } /*測試數(shù)據(jù)6 91 2 11 3 122 3 92 4 33 5 54 3 44 5 134 6 155 6 4*/

6 Wormholes

#include<iostream> #include<map> #include<queue> #include<algorithm> #include<cstring> #define inf 0x3f3f3f3f using namespace std; const int maxn = 505; int mp[maxn][maxn]; int n,m,w; void floyd() {for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(mp[i][j]>mp[i][k]+mp[k][j]) mp[i][j]=mp[i][k]+mp[k][j];}if(mp[i][i]<0){cout<<"YES"<<endl;return ;}}}cout<<"NO"<<endl; } int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int F;cin>>F;while(F--){cin>>n>>m>>w;memset(mp,inf,sizeof mp);for(int i=1;i<=n;i++)mp[i][i]=0;for(int i=0;i<m;i++){int u,v,p;cin>>u>>v>>p;if(p<mp[u][v])mp[u][v]=mp[v][u]=p;}for(int i=0;i<w;i++){int u,v,p;cin>>u>>v>>p;mp[u][v]=-p;}floyd();} } /*ВтЪдЪ§Он6 91 2 11 3 122 3 92 4 33 5 54 3 44 5 134 6 155 6 4*/

總結(jié)

以上是生活随笔為你收集整理的kuangbin专题-最短路练习的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。