HDU 4370 0 or 1 (최 단 로 djs)

[제목 링크]http://poj.org/problem?id=4370
제목
행렬 을 하나 드 리 겠 습 니 다. 0 과 1 로 구 성 된 행렬 을 찾 아 1. X12 + X13 +... X1n = 1 2. X1n + X2n +... Xn - 1n = 1 3. ＞ Xki (1 < = k < = n) = ＞ Xij (1 < = j < = n) 를 만족 시 킵 니 다.
문제 풀이 의 사고 방향.
수수께끼 같은 제목 의 뜻.전체적으로 행렬 을 그림 으로 보면 조건 1 은 노드 1 의 출 도 를 1 로 볼 수 있 고 조건 2 는 노드 n 의 입 점 을 1 로 볼 수 있 으 며 마지막 으로 조건 3 은 2 ~ n - 1 의 출 도 는 입 도 와 같다.위의 상황 을 만족 시 키 기 위해 1. 노드 1 에서 n 까지 의 가장 짧 은 길이 있다.2. 노드 1 은 자체 고 리 를 제외 한 고 리 를 찾 고 노드 n 은 자체 고 리 를 제외 한 고 리 를 찾는다.두 고리 의 총화.위의 두 가지 상황 중 하 나 는 조건 을 만족 시 키 는 최소 치 이다.
코드 부분

///                （        o(╥﹏╥)o）
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LL long long
#define inf 0x3f3f3f3
const int N = 305;
int n,m;
int maps[N][N]; 
int dis[N];
int vis[N];
struct node 
{
    int i,dis;
    friend bool operator < (node a,node b)  
    {
        return a.dis > b.dis;
    }
};
node add(int i,int dis)
{
    node t;
    t.i = i;
    t.dis = dis;
    return t;
}
void Dijkstra(int s)
{    
    priority_queueq;
    for (int i =1; i <= n; i++)
    {
        if (i == s)
            dis[i] = inf;
        else 
        {
            dis[i] = maps[s][i];
            q.push(add(i,dis[i]));
        }
        vis[i] = 0;
    }
    while (!q.empty())
    { 
        node t = q.top();
        q.pop();
        if (vis[t.i])  ///  i    
            continue;
        vis[t.i] = 1;
        for (int i = 1; i <= n; i++)
        {
            if (dis[i] > dis[t.i]+maps[t.i][i] && !vis[i])  ///   
            {
                dis[i] = dis[t.i]+maps[t.i][i];
                q.push(add(i,dis[i]));
            }
        }
    }
}
int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
                scanf("%d",&maps[i][j]);
        }
        Dijkstra(1);
        int ans = dis[n];
        int res = dis[1];
        Dijkstra(n);
        ans = min(ans,res+dis[n]);
        printf("%d
",ans);
    }
    return 0;
}