Sicily 1308 Dependencies among J(SOJ 1308)【BFS広さ優先検索】
原題アドレス:クリックしてリンクを開く
最初はトポロジーソートだと思っていましたが、似ているように見えたので、半分書いてから実際にこの問題のやり方が広捜と同じだと気づきました.
——————本文————
入力に基づいて有向図を作成し、目標点mからその直前ノードを前方に探し、これらの直前ノード(直前ノードを含む直前ノード)の時間値をすべて加算すればよい.
このようなノードをすべて探す方法は,広く検索する方法でキューを使用すればよい.
比較的簡単なテーマで、絵を描かない.
この問題はcinを使うとTLEになるかもしれません.また、行全体の入力についてはscanf("%[^],&s)を使っています.そのうち%[^]のような表現は正規表現に似ています.ええと、とにかく行全体の入力をどのように読み取るか知っていますが、文字列を数字に変換して、隣接表を使って優先関係を作り、最後にBFSを使えばいいです.
コードは次のとおりです.
******<転載説明>******転載明記:誠実な盗人原文住所:http://blog.csdn.net/fanfank/article/details/8952696******<転載説明/>******
最初はトポロジーソートだと思っていましたが、似ているように見えたので、半分書いてから実際にこの問題のやり方が広捜と同じだと気づきました.
——————本文————
入力に基づいて有向図を作成し、目標点mからその直前ノードを前方に探し、これらの直前ノード(直前ノードを含む直前ノード)の時間値をすべて加算すればよい.
このようなノードをすべて探す方法は,広く検索する方法でキューを使用すればよい.
比較的簡単なテーマで、絵を描かない.
この問題はcinを使うとTLEになるかもしれません.また、行全体の入力についてはscanf("%[^],&s)を使っています.そのうち%[^]のような表現は正規表現に似ています.ええと、とにかく行全体の入力をどのように読み取るか知っていますが、文字列を数字に変換して、隣接表を使って優先関係を作り、最後にBFSを使えばいいです.
コードは次のとおりです.
#include<stdio.h>
#include<vector>
#include<queue>
#include<memory.h>
#include<cstring>
#include<iostream>
#define BOUND 10005
using namespace std;
vector<int> v[BOUND];// v[i] i
queue<int> q;
long long t[BOUND]; //t[i] i
bool isv[BOUND];
int n,m;
char c,s[BOUND];
void toDigit(int index) //
{
int i=0,tmp=0;
while(i<strlen(s) && s[i]!=' ')
tmp=tmp*10+(s[i++]-'0');
i++;
t[index]=tmp;
for(;i<strlen(s);i++)
{
tmp=0;
while(i<strlen(s) && s[i]!=' ')
tmp=tmp*10+(s[i++]-'0');
v[index].push_back(tmp);
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d",&n) && n)
{
scanf("%d",&m);
scanf("%c",&c);
for(int i=0;i<=n;++i)
v[i].clear();
for(int i=1;i<=n;++i)
{
scanf("%[^
]",&s);
scanf("%c",&c);
toDigit(i);
}
memset(isv,0,sizeof(isv));
long long ans=t[m];
while(!q.empty())
q.pop();
q.push(m);
isv[m]=true;
while(!q.empty())
{
int qq=q.front();
q.pop();
for(int i=0;i<v[qq].size();++i)
{
int tmp=v[qq][i];
if(isv[tmp])
continue;
ans+=t[tmp];
q.push(tmp);
isv[tmp]=true;
}
}
printf("%lld
",ans);
}
}
******<転載説明>******転載明記:誠実な盗人原文住所:http://blog.csdn.net/fanfank/article/details/8952696******<転載説明/>******