5056: OI遊戲
Time Limit: 1 Sec Memory Limit: 64 MB
Description
小Van的CP最喜歡玩與OI有關的遊戲啦~小Van為了讨好她，于是冥思苦想，終于創造了一個新遊戲。
下面是小Van的OI遊戲規則：
給定一個無向連通圖，有N個節點，編号為0~N-1。圖裡的每一條邊都有一個正整數權值，邊權在1~9之間。
要求從圖裡删掉某些邊（有可能0條），使得剩下的圖滿足以下兩個條件：
1） 剩下的圖是一棵樹，有N-1條邊。
2） 對于所有v (0 < v < N)，0到v的最短路（也就是樹中唯一路徑長度）和原圖中的最短路長度相同。
最終要報出有多少種不同的删法可以滿足上述條件。（兩種删法不同當且僅當存在兩個點，
一種删法删完之後這兩個點之間存在邊而另外一種删法不存在。）
由于答案有可能非常大，良心的小Van隻需要答案膜1,000,000,007的結果。
後記： 然而這遊戲太高難度了，小Van的CP做不出來是以很不開心！
她認為小Van在故意刁難她，于是她與小Van分手了。。。
不過對于精通OI的你來說，這不過是小菜一碟啦！
Input
第一行一個整數N，代表原圖結點。
接下來N行，每行N個字元，描繪了一個鄰接矩陣。鄰接矩陣中，
如果某一個元素為0，代表這兩個點之間不存在邊，
并且保證第i行第i列的元素為0，第i行第j列的元素(i≠j)等于第j行第i列的元素。
2≤N≤50
Output
一行一個整數，代表删法總方案數膜1,000,000,007的結果。
Sample Input
Input1
2
01
10
Input2
4
0123
1012
2101
3210
Sample Output
Output1
1
Output2
6
題意：
求最小路徑樹計數。
題解：
直接spfa，求出每個點的最短路徑上的邊數目乘起來就可以了。
感性了解。。。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>
#define LL long long
#define mod 1000000007
#define N 55
using namespace std;
queue<int> q;
int n;
struct Edge{
int u, v, w, nxt;
}ed[];
int head[N], idc=;
char ss[N];
int dis[N];
bool vis[N];
void adde(int u, int v, int w){
ed[++idc].u = u;
ed[idc].v = v;
ed[idc].w = w;
ed[idc].nxt = head[u];
head[u] = idc;
}
int main(){
scanf("%d", &n);
for(int i=; i<=n; i++){
scanf("%s", ss+);
for(int j=; j<=n; j++)
if(ss[j] != '0') adde(i, j, ss[j]-'0');
}
memset(dis, , sizeof(dis));
dis[] = ; vis[] = ;
q.push( );
while(!q.empty()){
int u = q.front(); q.pop();
vis[u] = ;
for(int i=head[u]; i; i=ed[i].nxt){
int v = ed[i].v;
if(dis[v] > dis[u] + ed[i].w){
dis[v] = dis[u] + ed[i].w;
if( !vis[v] ) vis[v] = , q.push(v);
}
}
}
LL ans = ;
for(int u=; u<=n; u++){//root會被之後的統計到
LL tot = ;
for(int i=head[u]; i; i=ed[i].nxt){
int v = ed[i].v;
if(dis[u] == dis[v] + ed[i].w) tot++;
}//取這tot個路徑都可以保證u還有最短路徑
(ans *= tot) %= mod;
}
printf("%lld", ans);
return ;
}