題目鏈接：點擊查看

題目大意：給定一個n*n的矩陣，需要構(gòu)造出一個n*n的矩陣，規(guī)定矩陣只能由0或1組成，使得最小。

題目解析：題意很明確，但是卻很抽象，我們需要從圖論的角度來看待三個初始條件：

假設(shè)此時的n為4：

：表示點1的出度為1

：表示點n的入度為1

：表示點2~n-1的出度等于入度

初步分析得到三個條件可以等價于一條從1到n的最短路，權(quán)值為，而表示有向圖中的邊是否經(jīng)過，1表示經(jīng)過，0表示不經(jīng)

過因為在本題中權(quán)值非負(fù)，所以一定有一條最短路徑滿足題意

這樣就完了嗎？其實這里還有一個小細(xì)節(jié)值得注意，就是題目中只是描述了點1的出度和點n的入度，并沒有交代點1的入度和點n

的出度，所以他們不能默認(rèn)為0，那么意思就是他們可以各自組成一個環(huán)路（至少經(jīng)過一個點，即不能是自環(huán)，因為出度或入度

為1），比如這樣的一個矩陣X也是滿足題意的：

假設(shè)c1為點1自環(huán)的最短路，c2為點n自環(huán)的最短路，所以我們最后要求的答案就是min（d[n]，c1+c2）

在處理最短路部分初始化的時候要自己手動模擬第一次的運算，例如我們需要求d[1]，而正常的最短路都是將d[1]初始化為0，

而這個題中如果要求自環(huán)回到點1的最短路，我們需要將d[1]初始化為inf，直接上代碼吧，代碼更簡潔明了

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=310;int n;int maze[N][N];int d[N];bool vis[N];void spfa(int x) {queue<int>q;for(int i=1;i<=n;i++)//init{if(i==x){d[i]=inf;vis[i]=false;}else{d[i]=maze[x][i];q.push(i);vis[i]=true;}}while(!q.empty()){int tem=q.front();q.pop();vis[tem]=false;for(int i=1;i<=n;i++){if(d[i]>d[tem]+maze[tem][i]){d[i]=d[tem]+maze[tem][i];if(!vis[i]){q.push(i);vis[i]=true;}}}} }int main() { // freopen("input.txt","r",stdin);while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&maze[i][j]);spfa(1);int ans1=d[n];int ans2=d[1];spfa(n);ans2+=d[n];cout<<min(ans1,ans2)<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 4370 0 or 1(思维+最短路)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。