|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <iostream> #include <cstdio> #include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <queue> #include <cstdlib> #define INF 1000000000 #define ll long long using namespace std; int n,k; int flight_schedule_cost[11][11][40];//flight_schedule_cost[city][tocity][dayno]=cost of that day frm ct1 to cty 2 int periodOfCity[11][11]; ll dp[1010][15];//ll dp[day][citypath]; int kase=1; int costFromTheCity(int day,int startCity,int destination_city) { int schedulePeriod = periodOfCity[startCity][destination_city]; int dayOfschedule = day%(schedulePeriod); if(dayOfschedule==0) dayOfschedule=schedulePeriod; return flight_schedule_cost[startCity][destination_city][dayOfschedule]; } ll DP(int day,int city) { ll d; int cost; dp[1][1]=0; for(int i=1;i<=n;i++) dp[2][i]= (flight_schedule_cost[1][i][1]==0?INF : flight_schedule_cost[1][i][1]); for(int i=3;i<=(k+1);i++) { for(int j=1;j<=n;j++) { for(int kk=1;kk<=n;kk++) { if(j==kk) continue; if(dp[i-1][kk]==INF) continue; cost = costFromTheCity(i-1,kk,j); if(cost==0) continue; dp[i][j] = (dp[i-1][kk]+cost < dp[i][j] ? dp[i-1][kk]+cost : dp[i][j]); } } } return dp[k+1][n]; } int main() { int dailyCost; while(scanf("%d%d",&n,&k),n+k) { memset(flight_schedule_cost,0,sizeof(flight_schedule_cost)); memset(periodOfCity,0,sizeof(periodOfCity)); memset(dp,INF,sizeof(dp)); for(int i=0;i<1010;i++) for(int j=0;j<15;j++) dp[i][j]=INF; for(int start_city=1;start_city<=n;start_city++) { for(int destination_city=1;destination_city<=n;destination_city++) { if(destination_city==start_city) continue; scanf("%d",&periodOfCity[start_city][destination_city]); for(int dayNo=1;dayNo<=periodOfCity[start_city][destination_city];dayNo++) { scanf("%d",&dailyCost); flight_schedule_cost[start_city][destination_city][dayNo]=dailyCost; } } } ll tmp = DP(k+1,n); if(tmp!=INF) { printf("Scenario #%d\n",kase++); printf("The best flight costs %lld.\n\n",tmp); } else { printf("Scenario #%d\n",kase++); printf("No flight possible.\n\n"); } } return 0; } |