学步园

1001. http://acm.hdu.edu.cn/showproblem.php?pid=4370

神一样的题目，用图论的思想建模，建立1~n一共n各点。

X₁₂+X₁₃+...X_1n=1
2.X_1n+X_2n+...X_n-1n=1

理解为点1的出度为1，n点的入度为1；

将矩阵理解为边上的权值，那么可以理解为：

1. 从1到n的最短路

2.1和n各自的自环。

标程写了一个优先队列优化的dijikstra，orz一下，虽然忘记考虑自环了。

#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;

#define MAXN 330
#define INF 100000000

int n;
int dis[MAXN];
int g[MAXN][MAXN];

bool vis[MAXN];

priority_queue < pair<int,int> > pq;

int dijkstra()
{
	int i,S=0,T=n-1;
	vis[0]=dis[0]=0;
	pq.push(make_pair(0,S));
	for(i=1;i<n;i++) dis[i]=INF,vis[i]=false;
	while(!pq.empty())
	{
		int u=pq.top().second;
		pq.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(i=0;i<n;i++)
		{
			if(dis[i]>dis[u]+g[u][i])
			{
				dis[i]=dis[u]+g[u][i];
				pq.push(make_pair(-dis[i],i));
			}
		}	
	}
	return dis[T];
}

int main()
{
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
	while(~scanf("%d",&n))
	{
		int i,j;
		for(i=0;i<n;i++)
		for(j=0;j<n;j++) scanf("%d",&g[i][j]);
		printf("%d\n",dijkstra());
	}
	return 0;
}

自己写的dijisktra：明显挫很多啊

#include <cstdio>
#include <iostream>
using namespace std;

//复杂度是：O(N^2)
const int maxn = 330;
const int INF = (1 << 30);
int mat[maxn][maxn];

//s代表起点，d代表终点，N代表矩阵大小,不能处理负数
int dijkstra(int s, int d, int n) {
    bool vis[maxn];
    int dis[maxn], k  = INF, one = -1;
    memset(vis, false, sizeof(vis));
    fill(dis, dis + n, INF);
    vis[s] = true;
    dis[s] = 0;
    for(int i = 0; i < n; i++) dis[i] = mat[s][i];
    while(one != d) {
        k = INF;
        for(int i = 0; i < n; i++) if(dis[i] < k && !vis[i]) { one = i, k = dis[i]; }
        vis[one] = true;
        //cout << "here" << one << endl;
        for(int i = 0; i < n; i++) if(dis[i] > dis[one] + mat[one][i]) dis[i] = dis[one] + mat[one][i];
    }
    return dis[d];
}


int main() {
    int n;
    while(~scanf("%d", &n)) {
        for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%d", &mat[i][j]);
        for(int i = 0; i < n; i++) mat[i][i] = 0;
        printf("%d\n", dijkstra(0, n - 1, n));
    }
    return 0;
}