东北大学暑期acm夏令营 算法进阶第八天（图论专题）

部分内容参考：点我

第一题

#include<bits/stdc++.h>
using namespace std;
int n,e,a,b,ans;
bool check[15],flag;
vector<int>city[15];
struct point{
	int cityname,step;
}s,j;
void dfs(int fir,int end)
{
	check[fir]=true;
	s.cityname=fir,s.step=0;
	queue<point>q;
	q.push(s);
	while(!q.empty())
	{
		s=q.front();
		if(s.cityname==b)
		{
			ans=s.step;
			flag=true;
		}
		q.pop();
		for(int i=0;i<city[s.cityname].size();++i)
		{
			if(!check[city[s.cityname][i]])
			{
				check[city[s.cityname][i]]=true;
				j.cityname=city[s.cityname][i],j.step=s.step+1;
				q.push(j);
			}
		}
	}
}
int main()
{
	cin>>n>>e;
	while(e--)
	{
		cin>>a>>b;
		city[a].push_back(b);
		city[b].push_back(a);
	}
	cin>>a>>b;
	dfs(a,b);
	if(flag) printf("The length of the shortest path between %d and %d is %d.",a,b,ans);
	else printf("There is no path between %d and %d.",a,b);
} 

第二题（贪心，每次扔出来的最小点一定确定，只能他往别处走优化别处，不能别处来优化他）

#include<bits/stdc++.h>
using namespace std;
int n,e,a,ans[20005]; 
struct point{
	int dst,v;
	bool operator <(const point b) const {
        return v>b.v;
	}
}f,g;
vector<point>road[20005];
bool vis[20005];
void dfs(int str)
{
	priority_queue<point>q;
	f.dst=0;
	q.push(f);
	while(!q.empty())
	{
		f=q.top();
		q.pop();
		vis[f.dst]=true;
		for(int i=0;i<road[f.dst].size();i++)
		{
			g.dst=road[f.dst][i].dst;
			if(vis[g.dst])
			{
				continue;
			}
			ans[g.dst]=min(ans[g.dst],ans[f.dst]+road[f.dst][i].v);
			g.v=ans[g.dst];	
			q.push(g);
		}
	}
}
int main()
{
	cin>>n>>e;
	for(int i=1;i<n;i++)
	{
		ans[i]=INT_MAX;
	}
	while(e--)
	{
		cin>>a>>f.dst>>f.v;
		road[a].push_back(f);
	}
	dfs(0);
	bool first=false;
	for(int i=1;i<n;i++)
	{
		if(vis[i])
		{
			cout<<ans[i]<<" ";
		}
	}
}

第三题 （同上）

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,ans[2505],si,ti,w; 
struct point{
	int dst,v;
	bool operator <(const point b) const {
        return v>b.v;
	}
}qt,qs;
bool vis[2505];
vector<point>road[2505];
void dfs(int fir,int end)
{
	ans[fir]=0;
	qt.dst=fir;
	priority_queue<point>q;
	q.push(qt);
	while(!q.empty())
	{
		qt=q.top();
		q.pop();
		if(qt.dst==end)
		{
			return;
		}
		vis[qt.dst]=true;
		for(int i=0;i<road[qt.dst].size();i++)
		{
			qs.dst=road[qt.dst][i].dst;
			if(vis[qs.dst])
			{
				continue;
			}
			ans[qs.dst]=min(ans[qs.dst],ans[qt.dst]+road[qt.dst][i].v);
			qs.v=ans[qs.dst];
			q.push(qs);
		}
	}
}
int main()
{
	cin>>n>>m>>s>>t;
	for(int i=0;i<=n;i++)
	{
		ans[i]=INT_MAX;
	}
	while(m--)
	{
		cin>>si>>ti>>w;
		qt.dst=ti,qt.v=w;
		qs.dst=si,qs.v=w;
		road[si].push_back(qt);
		road[ti].push_back(qs);
	}
	dfs(s,t);
	cout<<ans[t];
}

第四题 （动态规划，不断看到其他点中转能不能更短）

#include<bits/stdc++.h>
using namespace std;
int ans[51][51],n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>ans[i][j];
			if(!ans[i][j]&&i!=j)
			{
				ans[i][j]=99999;
			}
		}
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				ans[i][j]=min(ans[i][j],ans[i][k]+ans[k][j]);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(ans[i][j]!=99999)
			{
				cout<<ans[i][j]<<" ";
			}
			else
			{
				cout<<-1<<" ";
			}
		}
		cout<<endl;
	}
}