POJ1502

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <climits>

using namespace std;

const int N = 105;

const int MAX = 0xfffffff;

int edge[N][N];

int n, e;

int s[N];

bool vis[N];

void init()

{

	for (int i = 0; i < n; ++i)

	{

		for (int j = 0; j < n; ++j)

		{

			edge[i][j] = -1;

		}

	}

	for (int i = 0; i < n; ++i)

	{

		vis[i] = false;

		s[i] = MAX;

	}

}

void dijkstra()

{

	int p, te, tm;

	s[0] = 0;

	vis[0] = true;

	p = 0;

	for (int i = 0; i < n - 1; ++i)

	{

		for (int j = 0; j < n; ++j)

		{

			if (!vis[j] && edge[p][j] != -1 &&  s[p] + edge[p][j] < s[j])

			{

				s[j] = s[p] +edge[p][j];

			}

		}

		tm = MAX;

		for (int j = 0; j < n; ++j)

		{

			if (!vis[j] && s[j] < tm)

			{

				tm = s[j];

				te = j;

			}

		}

		vis[te] = true;

		p = te;

	}

}

int change(char str[])

{

	if (str[0] == 'x') return -1;

	int ret = 0;

	while (*str)

	{

		ret = ret * 10 + *str++ - '0';

	}

	return ret;

}

int main()

{

	char str[35];

	int dis;

	scanf("%d", &n);

	init();

	for (int i = 0; i < n; ++i)

	{

		edge[i][i] = 0;

		for (int j = 0; j < i; ++j)

		{

			scanf("%s", str);

			dis = change(str);

			//cout<<*str<<" ";

			edge[i][j] = edge[j][i] = dis;

		}

	}

	dijkstra();

	int MAX = 0;

	for (int i = 1; i < n; ++i)

	{

		if (s[i] > MAX) MAX = s[i];

	}

	printf("%d\n", MAX);

	return 0;

}

POJ1502

题意：求单源最短路径，不过中间需要处理下特殊字符的情况，输入是个坑





输入：

n（点集）

n-1行

邻接矩阵下三角，x字符另外处理





输出：

源点到所有点最短路径中最大的值





解题思路：

单源最短路径有很多算法可以求解，简单一点的就是dij（N^2），另外可以用bellman-ford算法求，相应SPFA是对bellman-ford队列的优化，具体优化操作则是在存取队列节点时，不断进行松弛操作，直至队列为空。





贴上算法与实现书上用SPFA实现的代码以及floyd算法

#include <stdio.h>

#include <iostream>

#include <string.h>

#include <vector>

#include <math.h>

#include <queue>

#include <stdlib.h>

#define maxn 1000

#define INF 100000000

using namespace std;

vector < pair <int,int> > g[maxn+10];

char ch[10000],ans[100];

int node,edge,src;

int dis[maxn+10];

bool inQueue[maxn+10];

queue<int> que;

pair <int,int> suit;

void SPFA()

{

    for (int i=0; i<=node; i++)

        dis[i]=INF;

    memset(inQueue,false,sizeof(int)*(node+5));

    dis[src]=0;

    while(!que.empty())

    {

        que.pop();

    }

    que.push(src);

    inQueue[src]=true;

    while(!que.empty())

    {

        int u=que.front();

        que.pop();

        for(int i=0; i!=g[u].size(); i++)

        {

            if ( dis[u] + g[u][i].second <dis[g[u][i].first] )

            {

                dis[g[u][i].first] = dis[u] + g[u][i].second;

                if (!inQueue[g[u][i].first])

                {

                    inQueue[g[u][i].first] = true;

                    que.push(g[u][i].first);

                }

            }

        }

        inQueue[u]=false;

    }

}

int main()

{

    while( scanf("%d",&node)!=EOF )

    {

        getchar();

        for(int i=2; i<=node; i++)

        {

            gets(ch);

            int add,ji=1;

            char *p=ch;

            while(sscanf(p,"%s%n",ans,&add)!=EOF)

            {

                if(ans[0]=='x')

                {

                    ji++;

                    p=p+add;

                    continue;

                }

                suit.second=atoi(ans);

                suit.first=ji;

                g[i].push_back(suit);

                suit.first=i;

                g[ji].push_back(suit);

                p=p+add;

                ji++;

            }

        }

        src=1;

        SPFA();

        int max=-1;

        for(int i=1; i<=node; i++)

        {

            if( max < dis[i] )

                max=dis[i];

        }

        printf("%d\n",max);

    }

    return 0;

}

void floyd()

{

	for(int k=1;k<=n;k++)

		for(int i=1;i<=n;i++)

			for(int j=1;j<=n;j++)

				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);

}