最短路、邻接矩阵

这题拿到手里，我很是迷茫。
我不知道这道题该怎么做？刚开始认为是构造，看不出来图论模型。

原来，如果我们把给的矩阵看成图的邻接矩阵的话，那么我们就可以建立图论模型了。
正如题解所说。
condition1：节点1有一个出度
condition2：节点n有一个入度
condition3：节点2->n-1出度与入度相等

我们仔细想想哈，这不就是一条最短路吗！！！！！！1->n
关键的还有：如果形成环，就是形成一个以1为首尾的环和以n为首尾的环。
这也是满足上述条件的。
那么分这两种情况取小就可以了。

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
typedef pair<int,int> pii;
const int inf = 1e9;
const int max_n = 320;
const int max_m = 1e5+100;
int G[310][310];
int d[310];
int n;
int dijstra(int s,int t){
    priority_queue<pii,vector<pii>,greater<pii>> que;
    for (int i=0;i<=n;++i)d[i]=inf;
    que.push(pii(0,s));d[s]=0;
    while (!que.empty()){
        pii p = que.top();que.pop();
        int u = p.second;
        int dist = p.first;
        if (dist>d[u])continue;
        for (int v=1;v<=n;++v){
            if (v==u)continue;
            if (d[v]>dist+G[u][v]){
                d[v]=dist+G[u][v];
                que.push(pii(d[v],v));
            }
        }
    }return d[t];
}
int main(){
    while (~scanf("%d",&n)){
        for (int i=1;i<=n;++i)for (int j=1;j<=n;++j)scanf("%d",&G[i][j]);
        int ans = dijstra(1,n);
        int res1=inf,res2=inf;
        for (int i=2;i<n;++i)res1 = min(res1,d[i]+G[i][1]);
        dijstra(n,1);
        for (int i=n-1;i>1;--i)res2 = min(res2,d[i]+G[i][n]);
        ans = min(ans,res1+res2);
        cout<<ans<<endl;
    }
}