http://acm.timus.ru/problem.aspx?space=1&num=1085
簡單floy 不過有細節需要注意
首先是常識性的 tram 好像是環行的?? 還有就是如果有月票他不需要花錢但前提他要去的點有路可走
代碼:
#include<iostream> #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<vector> #include<set> #include<map> #include<string> #include<queue> #include<stack> #include <iomanip> using namespace std; #define LL long long const int INF=0x3f3f3f3f; //priority_queue<int,vector<int>,greater<int> >qt; const int N=105; int dist[N][N]; struct people { int money,s,k; }mem[N]; int main() { //freopen("data.in","r",stdin); for(int i=0;i<N;++i) for(int j=0;j<N;++j) if(i==j)dist[i][j]=0; else dist[i][j]=INF; int n,m,p; cin>>n>>m; int road[N]; while(m--) { int len; cin>>len; for(int i=0;i<len;++i) { cin>>road[i]; for(int j=0;j<i;++j) { dist[road[j]][road[i]]=4; dist[road[i]][road[j]]=4; } } } for(int l=1;l<=n;++l) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(dist[i][j]>dist[i][l]+dist[l][j]) dist[i][j]=dist[i][l]+dist[l][j]; /* for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) cout<<i<<"--->"<<j<<": "<<dist[i][j]<<endl; */ cin>>p; for(int i=0;i<p;++i) cin>>mem[i].money>>mem[i].s>>mem[i].k; int MIN=INF; int X=0; for(int i=1;i<=n;++i) { int tmp=0; for(int j=0;j<p;++j) { int s=mem[j].s; if(mem[j].k==1&&dist[s][i]!=INF) continue; if(mem[j].money<dist[s][i]) {tmp=INF;break;} //cout<<s<<" "<<i<<endl; //cout<<tmp<<" "<<dist[s][i]<<endl; tmp+=dist[s][i]; }//cout<<MIN<<" "<<tmp<<endl; if(tmp<MIN) { MIN=tmp; X=i; } } if(MIN==INF) cout<<"0"<<endl; else cout<<X<<" "<<MIN<<endl; return 0; }
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
