針對(duì)于poj1847這道題，總結(jié)一下最短路常用的四種模板.
**

Floyed（O(n^3)）

**

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ll long long #define inf 0x3f3f3f3f using namespace std;const int maxx=1e2+10; int mp[maxx][maxx]; int n,s,e;inline void floyed()//!!!核心代碼 {for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) mp[i][j]=min(mp[i][k]+mp[k][j],mp[i][j]);}} } int main() {scanf("%d%d%d",&n,&s,&e);int num,x;memset(mp,inf,sizeof(mp));for(int i=1;i<=n;i++){scanf("%d",&num);for(int j=1;j<=num;j++){scanf("%d",&x);if(j==1) mp[i][x]=0;else mp[i][x]=1;}}floyed();if(mp[s][e]==inf) cout<<"-1"<<endl;else cout<<mp[s][e]<<endl;return 0; }

**

Dijkstra（O(n^2)）

**

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #define ll long long #define inf 0x3f3f3f3f using namespace std;const int maxx=1e2+10; int mp[maxx][maxx]; int dis[maxx]; int vis[maxx]; int n,s,e;inline void dijkstra(int u)//核心代碼 {memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));dis[u]=0;for(int k=1;k<=n;k++){int _min=inf,v;for(int i=1;i<=n;i++){if(vis[i]) continue;if(dis[i]<_min) _min=dis[i],v=i;}vis[v]=1;for(int i=1;i<=n;i++){if(mp[v][i]!=inf&&vis[i]==0) dis[i]=min(dis[i],dis[v]+mp[v][i]);}} } int main() {scanf("%d%d%d",&n,&s,&e);int num,x;memset(mp,inf,sizeof(mp));for(int i=1;i<=n;i++){scanf("%d",&num);for(int j=1;j<=num;j++){scanf("%d",&x);if(j==1) mp[i][x]=0;else mp[i][x]=1;}}dijkstra(s);if(dis[e]==inf) cout<<"-1"<<endl;else cout<<dis[e]<<endl;return 0; }

**

Dijkstra（O(nlogn)）

**

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #define ll long long #define inf 0x3f3f3f3f using namespace std;const int maxx=1e2+10; struct node{int to,v;node(){}node(int a,int b){to=a,v=b;}bool operator<(const node &a)const{return v>a.v;} }; int mp[maxx][maxx]; int dis[maxx]; int vis[maxx]; int n,s,e;inline void dijkstra(int u)//核心代碼 {memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));dis[u]=0;priority_queue<node> q;q.push(node(u,0));while(q.size()){node a=q.top();q.pop();if(vis[a.to]) continue;vis[a.to]=1;for(int i=1;i<=n;i++){if(mp[a.to][i]!=inf&&dis[i]>dis[a.to]+mp[a.to][i]){dis[i]=dis[a.to]+mp[a.to][i];q.push(node(i,dis[i]));}}} } int main() {scanf("%d%d%d",&n,&s,&e);int num,x;memset(mp,inf,sizeof(mp));for(int i=1;i<=n;i++){scanf("%d",&num);for(int j=1;j<=num;j++){scanf("%d",&x);if(j==1) mp[i][x]=0;else mp[i][x]=1;}}dijkstra(s);if(dis[e]==inf) cout<<"-1"<<endl;else cout<<dis[e]<<endl;return 0; }

**

Spfa（未知）

**

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #define ll long long #define inf 0x3f3f3f3f using namespace std;const int maxx=1e2+10; int mp[maxx][maxx]; int dis[maxx]; int vis[maxx]; int n,s,e;inline void spfa(int u)//核心代碼 {queue<int> q;memset(vis,0,sizeof(vis));memset(dis,inf,sizeof(dis));vis[u]=1;dis[u]=0;q.push(u);while(q.size()){int v=q.front();q.pop();vis[v]=0;for(int i=1;i<=n;i++){if(mp[v][i]!=inf){if(dis[i]>dis[v]+mp[v][i]){dis[i]=dis[v]+mp[v][i];if(vis[i]==0){vis[i]=1;q.push(i);}}}}} } int main() {scanf("%d%d%d",&n,&s,&e);int num,x;memset(mp,inf,sizeof(mp));for(int i=1;i<=n;i++){scanf("%d",&num);for(int j=1;j<=num;j++){scanf("%d",&x);if(j==1) mp[i][x]=0;else mp[i][x]=1;}}spfa(s);if(dis[e]==inf) cout<<"-1"<<endl;else cout<<dis[e]<<endl;return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的最短路常用的四种模板（poj1847）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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