A - Til the Cows Come Home（spfa,Dijkstra,bellman_ford,DIjkastra優先隊列的優化)

Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible.

Farmer John's field has N (2 <= N <= 1000) landmarks in it, uniquely numbered 1..N. Landmark 1 is the barn; the apple tree grove in which Bessie stands all day is landmark N. Cows travel in the field using T (1 <= T <= 2000) bidirectional cow-trails of various lengths between the landmarks. Bessie is not confident of her navigation ability, so she always stays on a trail from its start to its end once she starts it.

Given the trails between the landmarks, determine the minimum distance Bessie must walk to get back to the barn. It is guaranteed that some such route exists.

Input

* Line 1: Two integers: T and N

* Lines 2..T+1: Each line describes a trail as three space-separated integers. The first two integers are the landmarks between which the trail travels. The third integer is the length of the trail, range 1..100.

Output

* Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N to landmark 1.

Sample Input

Sample Output

Hint

INPUT DETAILS:

There are five landmarks.

OUTPUT DETAILS:

Bessie can get home by following trails 4, 3, 2, and 1.

/*經典單源最短路問題，幾乎是闆子題
  這裡用的時Dijkstra算法；
  其他算法也可以做
*/ 
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define inf 0x3f3f3f
int visited[2005];
int G[2005][2005];
int n,m;
int dis[2005];
void Dijkstra(int v)
{
	for(int i = 1;i<=n;i++)//初始化dis和visited數組 
	{
		dis[i]=G[v][i];
		visited[i]=0;
	} 
	visited[v]=1;
	dis[v]=0;//從v開始 
	int minn,next;
	for(int i = 1;i<=n-1;i++)//每次存入一個點，需要n-1次操作 
	{
		minn=inf;
		for(int j = 1;j<=n;j++){//求出dis數組中最小的數，并得到其下标 
		    if(minn>dis[j]&&!visited[j]){
		  	   minn=dis[j];
		  	   next=j;
		    }	
		}
		if(minn==inf) break ;//兩個點不連通 
		visited[next]=1;
		for(int j = 1;j <= n;j++)//更新距離 
		   if(!visited[j]&&G[next][j]!=inf&&dis[next]+G[next][j]<dis[j])
		    dis[j]=dis[next]+G[next][j];
	}
	printf("%d\n",dis[n]);
} 
int main()
{
	while(scanf("%d %d",&m,&n)!=EOF)//注意是多執行個體，而且是先邊再點 
	{
		//初始化 
		for(int i = 1;i <= n;i++){
			for(int j = 1;j <= n;j++){
				G[j][i]=G[i][j]=(i==j)?0:inf;
			}
		}
		int s,e,w;
		for(int i = 0;i<m;i++){
			scanf("%d %d %d",&s,&e,&w);
			if(G[s][e]>w) G[s][e]=G[e][s]=w;//可能會有重複路徑 
		}
		Dijkstra(1);
	}
	return 0;
}

//bellman_ford做法 

#include <iostream>
#include<cstdio>
#define INF 0x3f3f3f3f 
using namespace std;
typedef struct Edge{
	int u,v;
	int cost;
}Edge;
Edge edge[2006];
int dis[2005];
int nodenum,edgenum; 
void bellman_ford()
{
	for(int i = 1;i<=nodenum;i++)
	   dis[i]=(i==1?0:INF);
	for(int i = 1;i<=nodenum-1;i++){
	    for(int j = 1;j<=edgenum;j++){	
	        if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cost)
	            dis[edge[j].v]=dis[edge[j].u]+edge[j].cost;
			if(dis[edge[j].u]>dis[edge[j].v]+edge[j].cost)
	            dis[edge[j].u]=dis[edge[j].v]+edge[j].cost;
		}
    }
}
int main(int argc, char** argv) {
	while(scanf("%d %d",&edgenum,&nodenum)!=EOF)
	{
	    for(int i = 1;i<=edgenum;i++)
	        scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].cost);
	    bellman_ford();
	    printf("%d\n",dis[nodenum]);	
	}
	 
	return 0;
}

//spfa做法 

#include <iostream>
#include<cstdio>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
typedef struct edge{
	int u,v,cost,next;
}Edge;
Edge edge[4005];
int edgenum,nodenum,headlist[2005];
void spfa()
{
	int i,dis[2005],v,visited[2005];
	queue<int> q;
	for(int i = 2;i<=nodenum;i++)
	{
		dis[i]=INF;
		visited[i]=0;
	}
	dis[1]=0;
	visited[1]=1;
	q.push(1);
	while(!q.empty()){
		v=q.front();q.pop();
		visited[v]=0;
		for(i=headlist[v];i!=-1;i=edge[i].next)
		    if(dis[v]+edge[i].cost<dis[edge[i].v]){
		    	dis[edge[i].v]=dis[v]+edge[i].cost; 
		    	if(!visited[edge[i].v]){
		    		visited[edge[i].v]=1;
		    		q.push(edge[i].v);
				}
			}
	}
	printf("%d\n",dis[nodenum]);
 } 
int main(int argc, char** argv) {
	int i,a,b,c;
	while(scanf("%d %d",&edgenum,&nodenum)!=EOF)
	{
		for(int i = 1;i<=nodenum;i++) headlist[i]=-1;
		for(int i = 1;i<=edgenum*2;i+=2){
			scanf("%d%d%d",&a,&b,&c);
			edge[i].u=a;
			edge[i].v=b;
			edge[i].cost=c;
			edge[i].next=headlist[a];
			headlist[a]=i;
			edge[i+1].u=b;
			edge[i+1].v=a;
			edge[i+1].cost=c;
			edge[i+1].next=headlist[b];
			headlist[b]=i+1;
		}
		spfa();
	}
	return 0;
}

//這裡是算法競賽入門紫皮書裡面的模闆spfa 

#include <iostream>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#define INF 0x3f3f3f3f
const int maxn=2005;
using namespace std;
struct Edge{
	int from,to,dist;
	Edge(int u,int v,int d):from(u),to(v),dist(d){};
}; 
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
int visited[maxn],cnt[maxn],dis[maxn],p[maxn];
void init(int n)
{
	for(int i = 0;i<=n;i++) G[i].clear();
	edges.clear();
}
void AddEdge(int from,int to,int dist)
{
	edges.push_back(Edge(from,to,dist));
	int m=edges.size();
	G[from].push_back(m-1);
}
bool spfa(int s)
{
	queue<int> q;
	memset(visited,0,sizeof(visited));
    memset(cnt,0,sizeof(cnt));	
	for(int i = 0;i<=n;i++) dis[i]=INF;
	visited[s]=1;
	dis[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		visited[u]=0;
		for(int i = 0;i<G[u].size();i++){
			Edge& e=edges[G[u][i]];
			if(dis[u]<INF&&dis[e.to]>dis[u]+e.dist){
				dis[e.to]=dis[u]+e.dist;
				p[e.to]=G[u][i];
				if(!visited[e.to]){
					q.push(e.to);
					visited[e.to]=1;
					if(++cnt[e.to]>n) return false;
				}
			}
		}
	}
	return true;
}
int main(int argc, char** argv) {
	while(scanf("%d %d",&m,&n)!=EOF){
		init(n);
		for(int i = 1;i<=m;i++){
			int u,v,w;
			scanf("%d %d %d",&u,&v,&w);
			AddEdge(u,v,w);
			AddEdge(v,u,w);
		} 
		
		if(spfa(1)) 
			  printf("%d\n",dis[n]);
	} 
	return 0;
}

//這裡是紫皮書裡面的Dijkstra優先隊列優化的做法
//平常的Dijkstra是O(n*n)複雜度的，這裡優化到了O(m*logn)(n代表節點個數，m代表邊的個數)
//是以該方法适用于稀疏圖(m遠小于n*n) 

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 2005;
int dis[maxn], pre[maxn];
struct Edge//邊 
{
    int u, v, w;
    Edge() {};
    Edge(int uu, int vv, int ww): u(uu), v(vv), w(ww) {};
};
vector<Edge> edges;//邊數組 
vector<int> G[maxn];//存儲每個節點對應的邊的序号 
void init(int nn)//清理 
{
    for(int i = 0; i <= nn; i++)
        G[i].clear();
    edges.clear();
}
void AddEdge(int uu, int vv, int ww)//加邊 
{
    edges.push_back(Edge(uu, vv, ww));
    int edgenum = edges.size();
    G[uu].push_back(edgenum - 1);
}
struct node//優先隊列優化，dis小的先出隊 
{
    int u, d;
    node() {};
    node(int uu, int dd): u(uu), d(dd) {};
    friend bool operator < (node a, node b)
    {
        return a.d > b.d;
    }
};
void dijkstra(int s)
{
    priority_queue<node> q;
    memset(dis, INF, sizeof(dis));//dis初始化為INF 
    dis[s] = 0;
    q.push(node(s, dis[s]));
    while(!q.empty())
    {
        node cur = q.top();
        q.pop();
        int from = cur.u;
        if(cur.d != dis[from])//減少了vis數組，表示該節點被取出來過 
            continue;
        for(int i = 0; i < G[from].size(); i++)//更新所有集合外點到集合的dis 
        {
            Edge e = edges[G[from][i]];
            if(dis[e.v] > dis[e.u] + e.w)
            {
                dis[e.v] = dis[e.u] + e.w;
                pre[e.v] = from;//存儲父節點 
                q.push(node(e.v, dis[e.v]));//将有更新的dis加入到隊列中 
            }
        }
    }
}
int main()
{
    int n, m;
    while(~scanf("%d%d", &m, &n) && n && m)
    {
        init(n);
        for(int i = 0; i < m; i++)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            AddEdge(u, v, w);
            AddEdge(v, u, w);
        }
        dijkstra(1);
        printf("%d\n", dis[n]);
    }
    return 0;
}

A - Til the Cows Come Home（spfa,Dijkstra,bellman_ford,DIjkastra優先隊列的優化)

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器