timus 1210 Kind Spirits(最短路)（动态规划）

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define inf 0x3f3f3f3f
#define mod 10000
typedef long long ll;
using namespace std;
const int N=1005;
const int M=50000;
int power(int a,int b,int c){int ans=1;while(b){if(b%2==1){ans=(ans*a)%c;b--;}b/=2;a=a*a%c;}return ans;}
int w[N][N],vis[N];
int n,m,k,c,s=1;
int sum[N],dp[N];
int main()
{
    memset(w,inf,sizeof(w));
    memset(dp,inf,sizeof(dp));
    sum[1]=1;
    char ch[2];
    scanf("%d",&n);
    for(int i=2;i<=n+1;i++){
        scanf("%d",&m);
        sum[i]=sum[i-1]+m;
        for(int j=1;j<=m;j++){
            while(~scanf("%d",&k)&&k){
                scanf("%d",&c);
                w[sum[i-2]+k][sum[i-1]+j]=c;
            }
        }
        if(i<=n)scanf("%s",ch);
    }
    dp[1]=0;
    for(int i=2;i<=n+1;i++){
        for(int j=sum[i-1]+1;j<=sum[i];j++){
            for(int k=sum[i-2]+1;k<=sum[i-1];k++){
                dp[j]=min(dp[j],dp[k]+w[k][j]);
            }
        }
    }
    int ans=inf;
    for(int i=sum[n]+1;i<=sum[n+1];i++){
        ans=min(ans,dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}