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元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
