http://ac.jobdu.com/problem.php?pid=1162? I Wanna Go Home

方法一：普通的dijkstra

/* 很明顯的最短路，但關鍵是如何建圖。可以看到，一共只有兩種走法，一種是從city1出發(fā)，一直走屬于group1的city直到city2，或者一直走屬于group2的city直到city1。我昨天建了兩個圖來表示兩種情況，分別求最短路，然后取小的，結果越寫越亂。今天發(fā)現其實一次就可以，只要在建圖的時候，如果兩個city屬于一個group，就建雙向圖，否則就建從屬于group1的city到屬于group2的city的單向圖。原因很簡單，因為兩種情況都不會出現從2到1的情況。建好圖然后就簡單了，注意無解的情況。 */ #include<iostream> #include<cstdio> using namespace std; #include<memory.h>int map[601][601],x[601]; int dijkstra(int n,int start,int end) //start是原點，n是圖中所有點的個數 {int visit[601]; //判斷是否已存入該點到visit集合中int i,j,k,min,t;for (i=1;i<=n;i++){x[i]=map[start][i];visit[i]=0; //初始都未用過該點}x[start]=0;visit[start]=1;// 依次將未放入visit集合的結點中，取x[]最小值的結點，放入集合visit中// 一旦visit包含了所有頂點，x就記錄了從源點到所有其他頂點之間的最短路徑長度// 注意是從第二個節(jié)點開始，第一個為源點for(i=2;i<=n;i++){min = 16843009;t=-1;// 找出當前未使用的點j的x[j]最小值for(j=1; j<=n; ++j){if(!visit[j] && x[j]<min){t = j; // t保存當前鄰接點中距離最小的點的號碼min = x[j];}}if(t!=-1){visit[t] = 1; // 將t點存入visit集合中// 更新x的值for(j=1; j<=n; ++j){if (!visit[j] && min+map[t][j]<x[j])x[j]=min+map[t][j];}}}if(x[end]<16843009)return x[end];elsereturn -1; } int main(void) {int i,j,n,m,from,to,cost,group[601];while(scanf("%d",&n),n){scanf("%d",&m);for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i==j)map[i][j]=0;elsemap[i][j]=16843009;}}//memset(map,1,sizeof(map));for(i=0;i<m;i++){scanf("%d %d %d",&from,&to,&cost);if(cost<map[from][to])map[from][to]=map[to][from]=cost;}for(i=1;i<=n;i++)scanf("%d",&group[i]);for(i=1;i<n;i++){for(j=i+1;j<=n;j++){if(group[i]==group[j]) //如果是一個group，不用管continue;else if(group[i]==1 && group[j]==2) //如果一個是1一個是2，則建單向邊 map[j][i]=16843009;else if(group[i]==2 && group[j]==1) //如果一個是1一個是2，則建單向邊 map[i][j]=16843009;}}printf("%d\n",dijkstra(n,1,2));}return 0; }

?方法二：優(yōu)先隊列+鄰接表 來實現dijkstra算法

/* 優(yōu)先隊列+鄰接表 來實現dijkstra算法 根據下面的那個模板來修改過來的 */ #include<iostream> #include<cstdio> #include<queue> using namespace std; #include<memory.h>#define INF 16843009 #define MAXN 601 //結點的個數typedef struct Edge {int adj;struct Edge *next;int cost; }Edge,*pEdge; Edge edge[MAXN];typedef struct Heap {bool operator <(Heap T)const{return T.dis<dis;}int x;int dis; }Heap;struct Node {int from,to,cost; }node[10001];void insert_adjlist(int a,int b, int c) //創(chuàng)建鄰接表 {pEdge p,q;p=&edge[a]; while(p->next!=NULL)p=p->next;q=new Edge;q->adj=b;q->next=NULL;q->cost=c;p->next=q; }int dijkstra(int n,int start,int end) //start是原點，n是圖中所有點的個數 {int i,x[MAXN];bool visit[MAXN];Heap cur,in;pEdge p;memset(visit,false,sizeof(visit));for(i=1;i<=n;i++)x[i]=INF;priority_queue< Heap >q; //優(yōu)先級隊列cur.x=start;cur.dis=0;x[start]=0;q.push(cur);while(!q.empty()){cur = q.top();q.pop();if(cur.x == end) //找到終點return cur.dis;if(visit[cur.x]) //訪問過continue;visit[cur.x]=true;p=edge[cur.x].next;while(p!=NULL){if(!visit[p->adj]){in.x=p->adj;in.dis=cur.dis+p->cost;if(in.dis<x[in.x]){x[in.x]=in.dis;q.push(in);}}p=p->next;}}return -1; }int main(void) {int i,j,n,m,from,to,group[601];while(scanf("%d",&n),n){scanf("%d",&m);for(i=1;i<=n;i++)edge[i].next=NULL;for(i=0;i<m;i++){scanf("%d %d %d",&node[i].from,&node[i].to,&node[i].cost); //暫時保存起來}for(i=1;i<=n;i++)scanf("%d",&group[i]);for(i=0;i<m;i++){from=node[i].from;to=node[i].to;if(group[from]==group[to]) //如果是一個group，建立雙向邊{insert_adjlist(from,to,node[i].cost);insert_adjlist(to,from,node[i].cost); }else if(group[from]==1 && group[to]==2) //如果一個是1一個是2，則建單向邊insert_adjlist(from,to,node[i].cost);else if(group[from]==2 && group[to]==1) //如果一個是1一個是2，則建單向邊insert_adjlist(to,from,node[i].cost); }printf("%d\n",dijkstra(n,1,2));}return 0; }

http://acm.hdu.edu.cn/showproblem.php?pid=2544?最短路

//優(yōu)先隊列+鄰接表 來實現dijkstra算法（模板） #include<iostream> #include<cstdio> #include<queue> using namespace std; #include<memory.h>#define INF 16843009 #define MAXN 601 //結點的個數typedef struct Edge {int adj;struct Edge *next;int cost; }Edge,*pEdge; Edge edge[MAXN];typedef struct Heap {bool operator <(Heap T)const{return T.dis<dis;}int x;int dis; }Heap;void insert_adjlist(int a,int b, int c) //創(chuàng)建鄰接表 {pEdge p,q;p=&edge[a]; while(p->next!=NULL)p=p->next;q=new Edge;q->adj=b;q->next=NULL;q->cost=c;p->next=q; }int dijkstra(int n,int start,int end) //start是原點，n是圖中所有點的個數 {int i,x[MAXN];bool visit[MAXN];Heap cur,in;pEdge p;memset(visit,false,sizeof(visit));for(i=1;i<=n;i++)x[i]=INF;priority_queue< Heap >q; //優(yōu)先級隊列cur.x=start;cur.dis=0;x[start]=0;q.push(cur);while(!q.empty()){cur = q.top();q.pop();if(cur.x == end)return cur.dis;if(visit[cur.x])continue;visit[cur.x]=true;p=edge[cur.x].next;while(p!=NULL){if(!visit[p->adj]){in.x=p->adj;in.dis=cur.dis+p->cost;if(in.dis<x[in.x]){x[in.x]=in.dis;q.push(in);}}p=p->next;}}return -1; }int main(void) {int i,j,n,m,from,to,cost,group[601];while(scanf("%d %d",&n,&m),n+m){for(i=1;i<=n;i++)edge[i].next=NULL;for(i=0;i<m;i++){scanf("%d %d %d",&from,&to,&cost);insert_adjlist(from,to,cost);insert_adjlist(to,from,cost); }printf("%d\n",dijkstra(n,1,n));}return 0; }

總結

以上是生活随笔為你收集整理的2011年北京大学计算机研究生机试真题（dijkstra+优先队列）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。